[인프런] 04_05 K번째 큰 수

📖  문제

---

• 첫 줄에 자연수 N(카드 수) K(몇 번째로 큰 수 찾을지) 입력
• 두 번째 줄 N개의 카드 값 입력
  •  N개의 카드 중 3장을 뽑을 수 있는 모든 경우의 수의 합을 기록
  • 기록한 값 중 K 번째로 큰 수를 출력하시오

 

출력 예시

⚠️  주의사항

---

• N개의 3장을 뽑을 수 있는 모든 경우의 수 이므로 다중 for문을 사용해야 합니다.
• 기록한 값 중의 K번째로 큰 수 이므로 저장할 때 TreeSet으로 저장하면 편합니다

 

✍️  이해

---

/**
 * 1. N장의 카드 K(몇 번째로 큰 것?) arr[N] 카드에 적힌 수
 * 2. TreeSet ts 생성
 * 3. 3중 for문으로 3개 뽑을 모든 경우의 수 ts.add
 * 4. ts에 있는 값들 for each 이용해서 비교하기
 *  4-1. cnt 값이 k 되면 answer = i 후 break;
 * 5. return answer; // 답이 없는경우 -1 출력이므로 answer = -1로 초기화 할 것
 */

TreeSet + Collections.reverseOrder()

✏️  풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public int solution(int N, int K, int[] arr) {

        TreeSet<Integer> ts = new TreeSet<>(Collections.reverseOrder()); 
        // TreeSet 값들 오름차순 정렬 (중복제거)
        // Collections.reverseOrder() N번째로 큰 값을 구해야하므로 내림차순 정렬이 편하다.
        
        
        // 3중 for문 3개의 합 모든 경우의 수 등록  
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    ts.add(arr[i] + arr[j] + arr[k]);
                }
            }
        }

        int cnt = 0;
        int answer = -1; // 없을 경우 -1 출력이므로 0으로 초기화x

        for (int i : ts) {
            cnt++;
            if(cnt == K) {
                answer = i;
                break; // 더이상 볼 필요 없으므로 빠져나갑니다.
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(T.solution(N, K, arr));
    }
}

---