[알고리즘] K번째 큰 수 with Java, set

오늘 배운 것

1. set 자료구조

. 중복 허용하지 않는 자료구조이다. 

2. sort

. stream()을 이용해서 정렬할 수 있다.

Set<Integer> arrayList = new HashSet<>();
List<Integer> collect = arrayList.stream().sorted().collect(Collectors.toList());

3. 문제 풀이

. 3중 포문으로 set에 넣어준다.

. 리스트로 변환하며 sorting해준 후, K번째 찾으면 끝.

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int N = kb.nextInt();
        int K = kb.nextInt();
        int [] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = kb.nextInt();
        }
        solution(K,arr);
    }

    private static void solution(int k, int[] arr) {
        Set<Integer> arrayList = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                for (int l = j+1; l < arr.length; l++) {
                    arrayList.add(arr[i]+arr[j]+arr[l]);
                }
            }
        }
        List<Integer> collect = arrayList.stream().sorted().collect(Collectors.toList());
        if(collect.size()<k){
            System.out.println("-1");
        }else{
            System.out.println(collect.get(collect.size()-k));
        }
    }
}

. 강의에서는 TreeSet을 이용하였다. 정렬에 효과적인 레드블랙트리를 사용하였다고 한다.

. stream을 이용해서 정렬하는 것이 아닌 cnt++ 을 통해 해결하셨다. 

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int N = kb.nextInt();
        int K = kb.nextInt();
        int [] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = kb.nextInt();
        }
        solution(K,arr);
    }

    private static void solution(int k, int[] arr) {
        TreeSet<Integer> arrayList = new TreeSet<>(Collections.reverseOrder());
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                for (int l = j+1; l < arr.length; l++) {
                    arrayList.add(arr[i]+arr[j]+arr[l]);
                }
            }
        }
        int cnt = 1;
        for(Integer i : arrayList){
            if(cnt++ == k){
                System.out.println(i);
                return;
            }
        }
        System.out.println("-1");
    }
}