[코딩연습_JAVA] K번째 큰 수

[간단 문제 설명]

1부터 100사이의 자연수가 적힌 N개의 카드(중복숫자 허용)에서 3장의 카드를 무작위로 골라 숫자를 더한다.

더한 숫자들 중 K번째로 큰 수를 출력한다. K번째 숫자가 없으면 -1을 반환한다.

 

 

자료의 중복을 허용하지 않으면서, value값은 필요 없고 key값만 있으면 되기 때문에

HashMap보다는 TreeSet을 활용하는 것이 좋다.

   public int solution(int n, int k, int[] arr){
       TreeSet<Integer> Tset=new TreeSet<>(Collections.reverseOrder()); //내림차순 정렬
       
       for (int i=0; i<n; i++){ //3개의 숫자를 합하여 TreeSet에 저장 
           for(int j=i+1; j<n; j++){
               for(int z=j+1; z<n; z++){
                   Tset.add(arr[i]+arr[j]+arr[z]);
               }
           }
       }
       int cnt=1;
       for(int x: Tset){
           if(cnt==k) return x; //k번째 수가 있을경우 그 수를 출력
           cnt++;
       }

       return -1; //k번째 수가 없을 경우 -1 반환
   }

 

 

 

 

[주요 개념]

집합 자료형(set)

: 집합 자료형으로는 HashSet, TreeSet, LinkedHashSet등이 있다.

 

특징

• 데이터의 중복을 허용하지 않음 (=중복을 허용하지 않는 자료를 다룰 때 유용함)
• 순서가 없음 (=list나 array처럼 순서가 없다. 따라서 index를 통해 값을 얻을 수 없다.)

 

TreeSet

: 이진탐색트리에 속하는 Red-Black Tree로 구현되어있다.

 

특징

• 데이터의 중복을 허용하지 않음
• 트리가 한쪽으로 치우치지 않고 균형을 유지함
• 값을 오름차순으로 정렬해 저장한다. (내림차순으로 정렬하고 싶으면 Collections.reverseOrder()를 사용하면 된다.)

         +) LinkedHashSet은 값을 입력한 순서대로 정렬한다.