자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : K번째 큰 수 (TreeSet)

 

https://hyejin.tistory.com/1230

자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 모든 아나그램 찾기

-> 이전 문제 풀이 

 

 

 

5. K번째 큰 수 

설명

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다.

현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다.

기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.

만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.

 

입력

첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다.

 

출력

첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.

 

예시 입력 1 

10 3
13 15 34 23 45 65 33 11 26 42

 

예시 출력 1

143

 

문제 풀이  1

public int solution(int n, int k, int[] arr) {
    int answer;
    Set<Integer> set = new TreeSet<>();

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int x = j + 1; x < n; x++) {
                set.add(arr[i] + arr[j] + arr[x]);
            }
        }
    }
    if (set.size() < k) {
        return -1;
    }

    answer =  set.stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList()).get(k - 1);

    return answer;
}

👩🏻‍💻 : 이 문제는 n 개의 카드가 주어지는데 이 카드 3개를 뽑아서 더하는데 이때 나올 수 있는 값들을 모두 구한 다음 

K 번째 큰 수의 값을 구하면 된다. (이때 중복된 값은 제외하고 K번째 수이므로 중복 제거를 이용해야 한다.)

 

중복 제거를 할 때 유용하게 사용할 수 있는 자료구조가 Set 이다. Set은 중복을 허용하지 않고, 순서 유지를 하지 않는데 

여기서 큰 수로 정렬해서 더하고 싶다면 TreeSet 을 이용하면 된다. 

 

삼중 for 문을 이용해서 arr[i] + arr[j] + arr[x] 의 합을 set에 add 해주고, 

k 가 set의 크기보다 크면 없다는 것이므로 -1 를 리턴해준다. 

 

TreeSet 에 add 한 값이 오름차순이니까 내림차순을 만들어줘야하는데... 나는 new TreeSet<> (Collections.reverseOrder()); 을 몰라서.. ^^ 생각났던 stream.sorted 사용 후, Comparator.reverseOrder()를 사용해줬다.. 

그 다음 Stream이므로 List 형태로 바꾼다음 get(k-1) 을 해서 answer 값을 구했다. (k-1) 번째부터 한 이유는 0 부터 get 하기 때문 !~ 

-> 이 부분은 약간의 뻘짓이 들어간 부분이다... 

 

 

문제 풀이  2

public int solution2(int[] arr, int n, int k) {
    int answer = -1;
    TreeSet<Integer> treeSet = 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++) {
                treeSet.add(arr[i] + arr[j] + arr[l]);
            }
        }
    }

    int cnt = 0;
    for (Integer integer : treeSet) {
        cnt++;
        if (cnt == k) return integer;
    }

    return answer;
}

👾 : 삼중 for문으로 treeSet에 세개의 합을 구해서 add하는 건 똑같은데 TreeSet을 생성할 때 Collections.reverseOrder()를 이용하면 내림차순으로 정렬해서 중복 제거해서 저장해준다..! 

 

그 다음 cnt 변수를 하나 선언해서 cnt +1  하면서 treeSet을 반복문으로 값을 구하는데 cnt 값이 k 값이 되면 그 값을 return 해주도록 했다. 

만약 이 반복문을 넘어서도 k 값을 구하지 못한다면 기본 answer 를 -1로 초기화해줬기 때문에 그대로 리턴해주면 된다. 

 

 

 

 

<TreeSet의 메서드>

public void solution3(int[] arr, int n, int k) {
    TreeSet<Integer> treeSet = 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++) {
                treeSet.add(arr[i] + arr[j] + arr[l]);
            }
        }
    }

    System.out.println("treeSet.size() = " + treeSet.size());
    treeSet.remove(143);
    System.out.println("treeSet.size() = " + treeSet.size());
    System.out.println("treeSet = " + treeSet);
    System.out.println("treeSet.first() = " + treeSet.first()); // 제일 앞의 수를 출력
    System.out.println("treeSet.last() = " + treeSet.last()); // 제일 마지막의 수를 출력
}

treeSet.size() : TreeSet의 크기를 구하는 메서드 

treeSet.remove() : 주어진 값을 TreeSet에서 제거하는 메서드 

treeSet.first() : treeSet의 제일 앞의 수를 출력 

treeSet.last() : treeSet의 제일 마지막 수를 출력 

 

결과 

treeSet.size() = 72
treeSet.size() = 71
treeSet = [152, 144, 141, 140, 136, 133, 132, 130, 125, 124, 123, 122, 121, 120, 118, 114, 113, 112, 111, 110, 109, 106, 105, 104, 103, 102, 101, 100, 99, 98, 94, 93, 92, 91, 90, 89, 88, 87, 86, 84, 83, 82, 81, 80, 79, 78, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 64, 62, 61, 60, 59, 58, 57, 54, 52, 51, 50, 49, 47, 39]
treeSet.first() = 152
treeSet.last() = 39