[인프런 알고리즘] Chapter 4, 5번 문제(K번째 큰 수)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

package inflearn_algorithm.chapter4;

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

public class sec04_05 {
    public static int solution(int N, int K , Integer[] arr) {
        int count = 1;
        TreeSet<Integer> reverseTreeSet = new TreeSet<>(Comparator.reverseOrder());
        for(int i = 0 ; i < N - 2 ; ++i)
        {
            for(int j = i + 1 ; j < N - 1 ; ++j)
            {
                for(int k = j + 1 ; k < N ; ++k) reverseTreeSet.add(arr[i] + arr[j] + arr[k]);
            }
        }

        for(Integer i : reverseTreeSet) if(count++ == K) return i;
        return -1;
    }

    public static void main(String[] args) throws IOException {
        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());
        Integer[] arr = new Integer[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, K, arr));
    }
}

 

 

 

설명

• TreeSet<Integer> reverseTreeSet = new TreeSet<>(Comparator.reverseOrder());를 사용하여 내림차순으로 정렬된 트리셋을 생성한다. 트리셋은 중복된 값을 허용하지 않으며, 자동으로 정렬된 상태를 유지한다.
  
  
• 중첩된 for 루프를 사용하여 배열에서 가능한 모든 세 숫자의 조합을 순회한다.
  arr[i] + arr[j] + arr[k]를 계산하여 그 합을 트리셋에 추가한다. 이는 i, j, k가 서로 다른 인덱스여야 한다. 트리셋에 추가되면서 자동으로 중복된 합이 제거되고, 내림차순으로 정렬된다.
  
  
• 트리셋의 요소들을 순회하면서, count 변수를 증가시킨다. count가 K와 같아지는 순간 해당 값을 반환한다.
  만약 K번째로 큰 값을 찾지 못하면 -1을 반환한다.