[TreeSet] 5. K번째 큰 수

5. K번째 큰 수

 

설명

현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다.

현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다.

기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.

만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.

입력

첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다.

출력

첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.

예시 입력 1 

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

예시 출력 1

143

 

 

<<풀이>>

 

일단 이 문제는 삼중 for문 사용하면 바로 구할 수 있다. 

 

하지만 삼중 for문 말고를 생각하다가 다른 경우를 생각 해봤는데 ㅋㅋ

 

강사님도 삼중 for문을 사용한다고 한다 ㅋㅋ 그래서 나는 삼중 for문을 활용하고 해쉬맵을 사용해서 넣은 뒤에 

 

그 값을 다시 keySet 메서드를 사용해서 풀고 정렬 또는 for문을 사용해서 풀 예정이었다.

 

다만!

 

이번에는 

중복제거와 정렬까지 해주는 TreeSet 을 활용해서 풀었다.

 

-강사님 풀이-

 

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

class Main {

    private int solution(int[] arr, int n, int m) {
        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 k = j + 1; k < n; k++) {
                    Tset.add(arr[i] + arr[j] + arr[k]);
                }
            }
        }

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

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

 

이렇게 TreeSet을 활용하면  HashMap을 사용하는 것보다 훨씬 더 간편하게 구할 수 있었다.

 

<<추가 풀이>>

 

TreeSet의 메서드

 

add() -> 값을 넣는다. 

 

remove() -> 들어있는 특정 값을 제거한다.

 

size() -> 원소의 갯수를 구할 수 있다.

 

first() -> 오름차순일 때에는 최소값을 반환하고 내림차순일 때는 최댓값을 반환한다. 일반적으로 제일 첫번째 인수를 반환한다.

 

last() -> fisrt와 반대이다.

 

isEmpty() -> 안에 값이 없으면 false 있으면 true를 반환한다.

 

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

 

Collections.reverseOrder() -> 내림차순으로 정렬한다. 

 

이거 없이 그냥 

TreeSet<Integer> Tset = new TreeSet<>();

 

를 사용하면 오름차순으로 정렬한다.

 

오늘도 제대로 배우고 간다!!