TreeSet_k번째 큰 수

✅ 1부터 100까지 적힌 n장의 카드를 가지고 있습니다.

이 카드 중 3장씩을 뽑아 더한 값을 기록합니다.
3장을 뽑을 수 있는 모든 경우의 수를 구합니다.
(따라서 순서대로 3장이 아니니 sliding window ❌)
기록한 값 중 k번쨰로 큰 값을 구하세요.
k번째로 큰 수가 존재하지 않으면 -1을 출력합니다.
단, 중복되는 경우 한 경우로 친다.
예를 들어, 25 25 23 23 21 이면 3번째로 큰 수는 21이 된다.

class Main {

    public int solution(int n, int k, int[] intArr){
       int answer= -1; //k번째 값이 존재하지 않으면 return -1
       int sum=0;
       Set<Integer> intSet= new TreeSet<>(Collections.reverseOrder()); //내림차순으로 정렬
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int l=j+1; l<n; l++){
                    sum= intArr[i]+ intArr[j] + intArr[l];
                    intSet.add(sum);
                }
            }
        }
        int count=0; //k번째 요소 찾기
        for(int num: intSet){
            count++;
            if(count ==k){
                answer=num;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int k=  sc.nextInt();
        int[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        System.out.print(T.solution(n, k, intArr));

    }
}
//⭐️input:
// 10 3
// 13 15 34 23 45 65 33 11 26 42
//⭐️output:
//143

🟢 .reverseOrder()은 Comparator안에도 있다.

class Main {

    public int solution(int n, int k, int[] intArr){
       int answer= -1;
       int sum=0;
       Set<Integer> intSet= new TreeSet<>(Comparator.reverseOrder()); //implements the Comparable interface
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int l=j+1; l<n; l++){
                    sum= intArr[i]+ intArr[j] + intArr[l];
                    intSet.add(sum);
                }
            }
        }
        int count=0; //k번째 요소 찾기
        for(int num: intSet){
            count++;
            if(count ==k){
                answer=num;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int k=  sc.nextInt();
        int[] intArr= new int[n];
        for(int i=0; i<n; i++){
            intArr[i] = sc.nextInt();
        }
        System.out.print(T.solution(n, k, intArr));

    }
}

🔵 ThingsILearned

✔️ Set은 중복을 허락하지 않는다.

List 중복 가능 ⭕️
Map 중복 가능 ⭕️ 에를 들어 key가 두개이면 value도 2가 되겠지?

✔️ HashSet 🆚 TreeSet

✔️ HashSet: Array

• add, remove, contains: O(1)
• 빠르고 효율적으로 더하고, 빼기 가능
  

✔️ TreeSet: Node

• maintains elements in sorted (ascending) order.
• implements the Comparable interface
• add, remove, contains: O(log n)
• 순서대로 정렬하여 찾아야 하는 문제

🔵 TreeSet methods

Set<Integer> treeSet= new TreeSet<>(); 일 때 (우선 오름차순으로 정렬됨)
✔️ treeSet.add()
✔️ treeSet.remove()
✔️ treeSet.size()
✔️ treeSet.first() 가장 첫 요소 구하기(오름차순 순일때는 가장 작은 수, 내림차순 순일때는 가장 큰 수곘지요?)
✔️ treeSet.last() 가장 마지막 요소 구하기(오름차순 순일때는 가장 큰 수, 내림차순 순일때는 가장 작은 수겠지요?)
✔️ Set<Integer> treeSet= new TreeSet<>(Collections.reverseOrder()); 내림차순으로 정렬

🟣 문제풀이 유형

순서대로 n개씩 돌기 ➡️ sliding window
여기서부터 여기까지 ➡️ two pointer

Key, value 값 있는가? ➡️ hashMap
중복되면 안 돼 ➡️ set ➡️ desc/asc ➡️ TreeSet