[TreeSet] K번째 큰 수 .java

설명

현수는 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

 

 

내 풀이

3장을 뽑을 수 있는 모든 경우를 기록해야한다 여기서 포인트는 중복 제거이다

=> TreeSet 사용 

 

1. TreeSet에 모든 경우의 수를 저장 -> 3중 for문으로 구현

2.  리스트로 TreeSet을 변환

3. k번째로 큰 수는 전체 리스트 길이에서 k를 빼면 오름차순으로 정렬했을 때의 등수임을 이용

 

TreeSet이 익숙하지 않아 중복제거를 위해서만 이용하고 나머지 과정은 ArrayList로 변환해서 구했다

 

import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        TreeSet<Integer> set = new TreeSet<>();
        //모든 경우 세기
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                for(int s = j+1; s < n; s++){
                    int sum = arr[i] + arr[j] + arr[s];
                    set.add(sum);
                }
            }
        }
        ArrayList<Integer> list = new ArrayList<>(set);
		
        //k번째가 list의 길이를 벗어나는지 검사
        if (list.size() >= k) {
            System.out.println(list.get(list.size() - k));
        } else {
            System.out.println(-1);  // K번째 수가 없을 경우 -1 출력
        

    }
}

 

 

 

다른 풀이

TreeSet(균형잡힌 이진 트리 구조)
중복 제거 + 자동 정렬

 

TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
내림차순 정렬

 

 

• TreeSet 자체를 내림차순 정렬로 구현
• for-each를 통해 하나씩 탐색
• 현재 인덱스 변수인 cnt를 활용하여 k번째의 값을 탐색 없으면 -1 

 

 

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

public class Main {
    public int solution(int n, int k, int[] arr){
        int answer = -1;

        //내림차순 정렬
        TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());


        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                for(int s = j+1; s < n; s++){
                    set.add(arr[i]+arr[j]+arr[s]);

                }
            }
        }
        //set.remove(값) -> 값 제거
        //System.out.print(set.size()); -> 값의 개수
        //System.out.print(set.first()); -> 오름차순이면 최솟값, 내림차순이면 최댓값 => 제일 처음 값
        //System.out.print(set.last()); -> 제일 마지막 값
        
        int cnt = 0;//현재 인덱스
        for(int x : set){
            cnt++;
            if(cnt == k){ return x;}
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        System.out.println(T.solution(n,k,arr));
    }
}

 

 

💡💡

트리셋을 잘 사용하지 않아 결국 리스트로 구현했는데 더 많은 문제를 풀어봐야겠다