(인프런)알고리즘문제풀이-4.5K번째 큰수

첫번째 아이디어

Set이라는 자료구조를 이용해서 중복을 제거한다.

TreeSet을 사용하면 중복을 제거하면서, 정렬까지 된다.

public int solution(int n, int k, int[] arr) {
        //10 3
        //13 15 34 23 45 65 33 11 26 42
        int answer = -1;
        TreeSet<Integer> tSet = new TreeSet<>(Collections.reverseOrder());

        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                for(int p=j+1; p<n; p++) {
                    tSet.add(arr[i]+arr[j]+arr[p]);//이렇게 해서 3가지를 뽑는 경우의수를 모두 더한다.
                }
            }
        }
        int cnt = 0;
        for(int x : tSet) {
            cnt++;
            if(cnt == k) {
                return x;
            }
        }

        return answer;
    }

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

• new TreeSet<>(Collections.reverseOrder()) 여기에서 Collections.reverseOrder()메서드를 이용해서 TreeSet에 저장되는데 내림차순으로 정렬되어 저장될 수 있도록 해준다.
• 위 문제는 주어진 배열에서 3가지를 골라서 합한 값을 뽑기 때문에 무조건 3중 포문을 이용했다.

🌟 reference

중복이 없어야하고, 정렬이 필요한 경우 TreeSet을 사용하면 좋다.
TreeSet을 이용하기 위한 메서드 설명

TreeSet을 정의할 때 new TreeSet<>(Collections.reverseOrder())

Collections.reverseOrder() 메서드를 이용하면 역순으로 정렬되어 저장할 수 있다.

TreeSet.remove(value)

value값을 넣어주면 TreeSet에 저장된 value값을 찾아서 삭제한다.

TreeSet.size()

안에 들어있는 원소의 갯수를 알려준다.

TreeSet.first()

오름차순인 경우 최소 값을 받고, 내림차순인 경우 최대 값을 받는다.
TreeSet에서 가장 앞에 있는 값을 받게 된다.

TreeSet.last()

오름차순인 경우 최대 값을 받고, 내림차순인 경우 최소 값을 받는다.
TreeSet에서 가장 끝에 있는 값을 받게 된다.

출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비