K번째 큰 수

 

문제 이해

 

카드들이 N장 나열되면, 이 중 3장을 뽑아 더한 값이 K번째로 큰 값을 출력하는 문제이다. 만약 K번째 수가 존재하지 않으면 -1을 출력하면 된다.

 

문제 해결

 

합을 큰 순서대로 나열하려면 만약 10 9 8 7 6 .. 이런 카드가 있다면 10 9 8 7 6 .. 10 9 8 7 6 .. 10 9 8 7 6 .. 10 9 8 7 6 ..

즉 일단 N장의 카드를 큰 순서대로 나열하고 3중 for문을 돌면서 합을 저장하고 원하는 k번째 set에 있는 합을 출력하는 방식대로 방법을 생각하며 시작했다.

 

우선 스캐너 객체를 생성하고 N, K를 입력받은 후 cards를 저장할 Integer 배열도 선언해주었다.

N만큼 for문을 돌며 카드들의 값들을 입력 받아준다.

Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
Integer[] cards = new Integer[N];

for (int i = 0; i < N; i++) {
    cards[i] = in.nextInt();
}

 

 

 

TreeSet을 내림차순 정렬로 생성해준 후 3중 for문을 둘며 3개의 수를 선택해서 더해 이를 Treeset sum에 더하고, 이는 내림차순, 즉 큰 수대로 정렬된다.

TreeSet<Integer> sum = new TreeSet<>(Collections.reverseOrder());
//65 45 42 34 33 26 23 15 13 11
for (int i = 0; i < N - 2; i++) { //3개를 포함할 수 있는만큼 반복
    for (int j = i+1; j < N - 1; j++) {//2개를 포함할 수 있는만큼 반복
        for (int k = j+1; k < N; k++) {//1개를 포함할 수 있는만큼 반복
            sum.add(cards[i] + cards[j] + cards[k]);
        }
    }
}

 

 

TreeSet이란?
TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스.
TreeSet은 정렬 조건을 지정하여 선언이 가능하기에 이번 같은 문제에 적합!

 

 // TreeSet 생성 (default:오름차순) 
TreeSet<type> tree = new TreeSet<>();

 // 컬렉션을 저장하는 TreeSet 생성 (default:오름차순)
TreeSet<type> tree = new TreeSet<>(Collection c);

// 내림차순 정렬로 TreeSet 생성​
TreeSet<type> tree = new TreeSet<>(Collections.reverseOrder()); 

 

 

 

count 변수를 설정해준 후, sum을 하나씩 돌며 count를 증가시켜준다. sum에는 이미 큰 수대로 정렬되어있기 때문에, count가 K가 될 때의 s를 출력하고 프로그램을 종료해주면 된다.

만약 K번째의 수가 없다면 -1을 출력해준다.

int count = 0;
    for (Integer s : sum) {
        count++;
        if (count == K) {
            System.out.println(s);
            return;
        }
    }

    System.out.println(-1);
}

 

최종 코드

 

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;
public class P05_K번째큰수 {
    public static void main(String[] args) {
        //큰 순서대로 정렬해놓고
        //3중 for문 돌면서 합 저장하고, 원하는 k번째 set에 있는 합 출력하는 방식으로

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        Integer[] cards = new Integer[N];

        for (int i = 0; i < N; i++) {
            cards[i] = in.nextInt();
        }

        Arrays.sort(cards, Collections.reverseOrder()); //큰 순서대로 정렬

        TreeSet<Integer> sum = new TreeSet<>(Collections.reverseOrder());
        //65 45 42 34 33 26 23 15 13 11
        for (int i = 0; i < N - 2; i++) { //3개를 포함할 수 있는만큼 반복
            for (int j = i+1; j < N - 1; j++) {//2개를 포함할 수 있는만큼 반복
                for (int k = j+1; k < N; k++) {//1개를 포함할 수 있는만큼 반복
                    sum.add(cards[i] + cards[j] + cards[k]);
                }
            }
        }
        int count = 0;
        for (Integer s : sum) {
            count++;
            if (count == K) {
                System.out.println(s);
                return;
            }
        }

        System.out.println(-1);
    }
}