Q4 - 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

 

 

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int in1 = in.nextInt();
		int in2 = in.nextInt();
		int[] in3 = new int[in1];
		for(int i = 0; i<in1; i++) {
			in3[i] = in.nextInt();
		}
		
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i<in1; i++){
            for(int k =i+1; k<in1; k++){
                for(int t = k+1; t<in1; t++){
                    map.put(in3[i]+in3[k]+in3[t], map.getOrDefault(in3[i]+in3[k]+in3[t], 0)+1);  
                }
            }
        }
      Object[] mapkey = map.keySet().toArray();

        Arrays.sort(mapkey, Collections.reverseOrder());
        int count = 0;
        for(Object i : mapkey){
            count++;
            if(count == in2){
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);    
        in.close();

                 
//		Scanner in = new Scanner(System.in);
//		int in1 = in.nextInt();
//		int in2 = in.nextInt();
//		int[] in3 = new int[in1];
//		for(int i = 0; i<in1; i++) {
//			in3[i] = in.nextInt();
//		}
//        int cnt=0;
//        //tSet.remove(143); 143 지워!
//        //tSet.first(); ///오름차순이면 가장 작은수 내림차순이면 가장 큰 수 출력
//        ///tSet.last();
//        for(int x : tSet){
//            cnt++;
//            if(cnt==in2) System.out.println(x);
//        }
//              
//        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
//        for(int i = 0; i<in1; i++){
//            for(int k =i+1; k<in1; k++){
//                for(int t = k+1; t<in1; t++){
//                    map.put(i+k+t, map.getOrDefault(i+k+t, 0)+1);  
//                }
//            }
//        }
//      Object[] mapkey = map.keySet().toArray();
//        Arrays.sort(mapkey);
//        if(mapkey[in2-1] == null){
//            System.out.println(-1);    
//        }else{
//            System.out.println(mapkey[in2-1]);    
//        }
//        
//        System.out.println(-1);
//        in.close();
//        return;
	}

}

 

import java.util.*;
class Main {	
	public int solution(int[] arr, int n, int k){
		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 l=j+1; l<n; l++){
					Tset.add(arr[i]+arr[j]+arr[l]);
				}
			}
		}
		int cnt=0;
		//Tset.remove(143);
		//System.out.println(Tset.size());
		//System.out.println("first : "+ Tset.first());
		//System.out.println("last : "+ Tset.last());

		for(int x : Tset){
			//System.out.println(x);
			cnt++;
			if(cnt==k) return x;
		}
		return answer;
	}

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