K번째 큰 수 / TreeSet

설명

현수는 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

import java.util.*;
//K번째 큰 수
public class Main {
    public static int solution(int N, int K, int[] arr) {
        int sum;
        HashMap<Integer, Integer> map = new HashMap<>();
        //nC3 조합의 합들 map에 저장
        for (int i = 0; i < arr.length - 2; i++) {
            for (int j = i + 1; j < arr.length - 1; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    sum = arr[i] + arr[j] + arr[k];
                    map.put(sum, map.getOrDefault(sum, 0) + 1);
                }
            }
        }

        Map<Integer, Integer> sortedMap = new TreeMap<>(map);//treeMap을 이용하여 오름차순 정렬
        int ans = -1;

        int cnt = 0;
        for (Integer key : sortedMap.keySet()) { //키 루프시키며 K번째로 큰 수 찾기
            if (cnt == sortedMap.size() - K) {
                ans = key;
            }
            cnt++;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(N,K,arr));
    }
}

 

소스 코드2

import java.util.*;

//K번째 큰 수 다른 풀이
public class Main {
    public static int solution(int N, int K, int[] arr) {
        int ans = -1;
        TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder()); // 기본적으로 오름차순이지만 reverseOrder를 이용하여 내림차순으로 정
        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                for (int k = j + 1; k < N; k++) {
                    Tset.add(arr[i] + arr[j] + arr[k]);
                }
            }
        }

        int cnt = 0;
        for (Integer x : Tset) {
            cnt++;
            if (cnt == K) {
                return x; //K번째 수 리턴
            }
        }

        return ans; //K값이 존재 안하면 -1 리턴
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(N,K,arr));
    }
}

 

 

TreeSet

 - TreeSet<Integer> Tset = new TreeSet<>(); 와 같이 선언한다.

  - 위의 경우 기본적으로 오름차순으로 정렬됨.

  - 내림차순으로 정렬하고 싶을 때는 new TreeSet<>(Collections.reverseOrder()); 로 선언하면 된다.

 

- add

  - Tset.add(1) : Tset에 1 추가

 

- remove

  - Tset.remove(1) : Tset에 있는 1 삭제

 

 - size

  - Tset.size() : Tset의 사이즈(개수)를 알려준다.

 

 - first

  - Tset.first() : Tset에서 제일 앞에 있는 값을 알려준다. 기본은 오름차순이므로 제일 작은 수 출력

 

 - last

  - Tset.last() : first와 반대로 제일 뒤에 있는 값을 알려준다.

 

 - TreeMap은 정렬을 할 때 이용하고 TreeSet은 보통 중복제거를 할 때 사용한다.