[Ch.04 - HashTree] 05. K번째 큰 수 # (+ TreeSet)

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

 

---

Set 자료구조 : 중복을 제거한 자료구조

HashSet<Integer> set = new HashSet<>();

 

TreeSet 자료구조 : 중복을 제거하고, 오름차순 정렬을 한 자료구조

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

 

 

-> 내림차순 정렬을 할 경우

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

 

 

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

public class Main {
	public int solution(int m, int[] arr) {
		int answer=-1;
		TreeSet<Integer> Tset = 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++) {
					Tset.add(arr[i]+arr[j]+arr[l]);
				}
			}
		}
		int cnt=0;
		for(int x: Tset) {
			cnt++;
			if(cnt==m) return answer=x;
		}
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int [] arr =new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		System.out.println(T.solution(m,arr));
	}

}

 

Iterator를 이용할 경우

package hashtree04_2;

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

public class Hashtree05 {
	public int solution(int m, int[] arr) {
		int answer=-1;
		TreeSet<Integer> Tset = 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++) {
					Tset.add(arr[i]+arr[j]+arr[l]);
				}
			}
		}
		Iterator<Integer> iter = Tset.iterator();
		int cnt=0;
		while (iter.hasNext()) {
			int key = ((int) iter.next());
			cnt++;
			if(cnt==m) return answer=key; 
			
		}
		return answer;
	}
	public static void main(String[] args) {
		Hashtree05 T = new Hashtree05();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int [] arr =new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		System.out.println(T.solution(m,arr));
	}

}

---

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] arr =new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    System.out.println(Solution(n,k,arr));
  }
  private static int Solution(int n, int k, int[] arr){
    int answer=-1;
    //TreeSet
    Set<Integer> set = new TreeSet<>(Collections.reverseOrder());

    for(int i=0;i<n;i++){
      for(int j=i+1; j<n;j++){
        for(int m=j+1; m<n;m++){
          int sum=0;
          sum+=arr[i];
          sum+=arr[j];
          sum+=arr[m];
          set.add(sum);
        }
      }
    }
    int cnt=1;
    for(int x:set) {
      if(cnt==k) {
        return answer=x;
      }
      cnt++;
    }
    return answer;
  }
}

---

+)03.03

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    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();
    }
    Main main = new Main();
    System.out.println(main.solution(arr,n,m));
  }
  public int solution(int[] arr, int n, int m){
    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 k=j+1; k<n;k++){
          set.add(arr[i]+arr[j]+arr[k]);
        }
      }
    }
    int cnt=1;
    for(int x:set){
      if(cnt==m)answer=x;
      cnt++;
    }
    
    return answer;
  }
}