🧔K번째 큰 수

👧문제

• 입력값 2개를 받는다. 예를 들어 10 3 이라고 하면, 10개의 숫자를 입력하고, 3장을 뽑아 더한 값들 중 3번째로 큰 수를 출력하는 프로그램이다.

👧 풀이

🕵️‍♀️ step1) 3개의 합을 어디에 저장할 것인가?

🧟‍♀️ TreeSet - 범위 탐색, 정렬

• TreeSet이란? 범위 탐색, 정렬
  이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리

• 이진트리(binary tree) : B와 C의 부모는 A
• 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

🧟‍♀️ 이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
  
• 위와 같은 특징 때문에 데이터가 많아질 수록 추가, 삭제에 대한 시간이 더 걸린다.(비교 횟수 증가)
  

🧟‍♀️ TreeSet 데이터 저장과정 boolean add(Object O)

TreeSet에 3개의 합을 저장하자.

TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder);

🕵️‍♀️ step2) 3개의 합을 어떻게 treeset에 저장할 것인가?

3중 for문을 이용해서 저장하도록 하자.

for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
    	for(int l=0;l<n;l++){
        	Tset.add(arr[i]+arr[j]+arr[l]);
        }
    }
}

🕵️‍♀️ step3) 입력한 값 K번째로 큰 값을 어떻게 뺄 것인가?

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

👧 소스코드

package algolecture;

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

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

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