section4.5

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

 

 

 

ANSWER

public class Question5 {
    public static void main(String[] args) {
        Question5 T = new Question5();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        
        System.out.println(T.Solution(n, k, arr));
    }

    public int Solution(int n, int k, int[] arr) {
        List<Integer> tmplist = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tmplist.add(arr[i]);
        }
        Collections.sort(tmplist,  Collections.reverseOrder());
        System.out.println("tmplist : "+tmplist);
        return getSumForThree(tmplist, k);
    }

    public int getSumForThree(List<Integer> arr, int k) {
        HashSet<Integer> sumList = new HashSet<>();
        List<Integer> rslt = new ArrayList<>();
        int totalSize = arr.size();

        for (int i = 0; i < totalSize; i++) {
            for (int j = i + 1; j < totalSize; j++) {
                for (int s = j + 1; s < totalSize; s++) {
                    sumList.add(arr.get(i) +arr.get(j) + arr.get(s));
                }
            }
        }
        rslt = new ArrayList<>(sumList);
        Collections.sort(rslt, Collections.reverseOrder());

        return rslt.get(k-1);
    }
}

정답은 맞았지만, 시간 초과가 나왔다

 

 

 

SOLUTION

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

        int cnt = 0;
        for (int x : tSet) {
            cnt ++;
            if (cnt == k) {
                return x;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Answer5 T = new Answer5();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(arr, n, k));
    }
}

정답은 TreeSet을 이용해 풀었다

TreeSet은 알고 있었지만 (중복 + 순차정리) 두 가지 기능이 있는지 까먹었고 그나마 중복 제거 할 수 있는 HashSet을 사용한 거였다

 

이왕 TreeSet을 정리하자면...

• Set 인터페이스를 구현한 클래스로 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다
• TreeSet은 이진탐색트리의 구조로 이루어져 있다
• 이진탐색트리는 추가/삭제에는 시간이 걸리지만, 정렬/검색에 높은 성능을 보이는 자료 구조