N장의 카드에서 3장 뽑고 그 합이 k번째로 큰 수 구하기

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

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

기록한 값 중 K번째로 큰 수를 출력하세요.

 

입력예시 

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

 

답 : 143

 

나의 답변

public class Main {	
	public int solution(int n, int k, int[] arr) {
		int answer=-1; 
		TreeSet<Integer> ts = new TreeSet<>(Collections.reverseOrder());
		for( int i=0 ; i<n; i++) {
			for( int j=i+1; j<n; j++ ) {
				for( int t=j+1; t<n; t++) {
					ts.add(arr[i]+arr[j]+arr[t]);
				}
			}
		}
		int cnt=0; 
		for( int x : ts ) {
			cnt++; 
			if( cnt == k ) answer=x;
		}
		return answer; 
		
	}
	public static void main(String[] args) {
		Main T = new Main();
		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.print(T.solution(n, k, arr));
	}
}

 

 

• 카드를 3장 뽑아야 하므로 3중 for문을 사용햔다.
• 3장을 뽑을 수 있는 모든 경우를 기록하는데 중복은 허용하지 않아야 명확한 k번째로 큰 수를 알 수 있다.
• Set 인터페이스는 순서를 유지하지않고 중복을 허용하지 않는 인터페이스다. ( HashSet / Treeset )
• TreeSet은 정렬, 빠른 검색, 범위 검색에 적합하다. 
• 내림차순을 위해 Collections.reverseOrder() 사용