[알고리즘]TreeSet - K번째 큰 수

5. K번째 큰 수
기록한 값 중 K번째로 큰 수를 출력하는 프로그램

1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다.
이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다.
입력) 첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50)가 입력되고, 그 다음 줄에 N개의 카드값이 입력됩니다.
출력) 첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.

 

 

1)

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

public class Main { // TreeSet : 중복제어 + 정렬 // add()
	
	public static int solution(int n, int k, int[] arr) {
		int answer = -1;
		TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder()); // 내림차순
		
		// 3개 뽑아서 합 구해 Tset에 추가
		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; // k번째
		}
		return answer;
	}

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

}

Collections.reverseOrder() -> 내림차순으로 자동 정렬

 

2)

import java.util.NavigableSet;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	
	public static int solution(int n, int k, int[] arr) {
		int answer = -1, sum = 0;
		TreeSet<Integer> treeSet = new TreeSet<>(); 
		
		for (int i=0; i<n; i++) {
			sum = 0;
			for (int j=0; j<n; j++) {
				for (int q=0; q<n; q++) {
					if (i!=j && j!=q && q!=i) {
						sum = arr[i] + arr[j] + arr[q];
						treeSet.add(sum);
					}
				}
			}
		}
		NavigableSet<Integer> desSet = treeSet.descendingSet(); // 내림차순
		
		if (k<=treeSet.size()) {
			for (int i=0; i<k-1; i++) {
				desSet.remove(desSet.first());
			}
			answer = desSet.first();
		}
		return answer;
	}

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

}

---

결과

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

출력
143