섹션 4. HashMap, TreeSet - 5. K번째 큰 수

 

📌 문제 설명

1부터 100 사이의 자연수가 적힌 N장의 카드 중, 3장을 뽑아 합한 값을 모두 기록한 뒤, 그 중 K번째로 큰 수를 구하는 문제입니다.

• 같은 숫자의 카드가 여러 장 있을 수 있습니다.
• 모든 조합의 합을 고려하고, 중복된 합은 제거한 뒤 K번째 수를 찾습니다.

---

📝 입력 & 출력

입력

• 첫째 줄: 자연수 N (3 ≤ N ≤ 100), K (1 ≤ K ≤ 50)
• 둘째 줄: N개의 카드 숫자 (1 ~ 100)

출력

• K번째로 큰 수 출력 (존재하지 않으면 -1 출력)

---

🔸 예제 입력 & 출력

예제 입력 1

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

 

예제 출력 1

143

 

---

💡 해결 방법

• 중복된 합을 제거하면서 내림차순 정렬된 순서로 저장하기 위해 TreeSet 사용
• 3중 for문으로 가능한 모든 3장의 카드 합을 TreeSet에 저장
• TreeSet은 자동 정렬되므로, 반복문을 돌면서 K번째 값을 찾으면 된다

✅ TreeSet이란?

• 중복을 허용하지 않고 자동 정렬되는 자료구조
• TreeSet<>(Collections.reverseOrder())로 내림차순 정렬 가능
• 삽입, 삭제, 탐색 모두 O(logN)

---

💻 코드 구현 (Java)

package partHashTree;

import java.util.*;

public class Problem5 {
	public int solution(int n, int k, int[] arr) {
		int result = -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 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 result;
	}

	public static void main(String[] args) {
		Problem5 T = new Problem5();
		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.print(T.solution(n, k, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 3중 for문으로 모든 조합 구하기

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]);
		}
	}
}

• 서로 다른 3장의 카드를 고르는 모든 경우의 수 → 조합 (nC3)

2️⃣ TreeSet을 순회하며 K번째 수 찾기

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

• TreeSet은 자동 정렬되므로, K번째 원소를 순서대로 찾을 수 있음

---

⏳ 시간 복잡도 분석

• 3중 반복문: O(N³) → 최대 N=100이면 약 1,000,000번 연산
• TreeSet에 삽입: O(logM) (M은 가능한 합의 개수)
• 실질적으로 100 이하이므로 충분히 1초 안에 수행 가능

---

🎯 결론

• 조합 문제 + 정렬된 순위 접근 시 TreeSet 활용이 매우 유용
• 중복 제거 + 자동 정렬을 동시에 처리해주는 자료구조
• N이 작을 경우 완전탐색 + 트리셋 조합으로 깔끔하게 해결 가능

---

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

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런