[JAVA] K번째큰수

문제

 

풀이

카드 3개의 합을 중에서 K번째로 높은 값을 구해야하는 문제이다. 우선 여러 카드 중에서 3개의 카드를 뽑는 건 3중 For문을 사용해서 할 수 있다. 그리고 그렇게 3개의 카드를 더한 값을 저장해야한다. 하지만 문제가 있는데 이렇게 뽑은 값들에 중복이 있다. 따라서 중복을 제거하기 위해 Set 자료구조를 사용할 것이다. 그리고 k번째로 높은 합을 구할거니깐 TreeSet을 사용한다. TreeSet은 안의 원소가 오름차순으로 정렬되어있다. 

코드

package 인프런.해시맵과트리셋.K번째큰수.방법1;

import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    private int solution(int n, int m, int[] arr) {
        int answer = -1;    // 만약 k번째 수가 존재하지 않으면 -1
        TreeSet<Integer> set = 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++) {
                    set.add(arr[i] + arr[j] + arr[l]);
                }
            }
        }
        int index = 0;  // 원소 순서를 추적하기 위한 변수
        for (int x : set) {
            index++;
            if (index == m) return x;
        }

        return answer;
    }

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

느낀점

Set에대한 특징을 알 수 있었던 문제. Set은 원소값이 중복되는것을 허용하지 않는다. 그리고 TreeSet의 경우 원소는 정렬상태에 있다.

만약 내림차수으로 바꾸고 싶으면 생성자에 Collections.reverseOrder()을 넣어주면 된다.