[문제풀이] 04-05. K번째 큰 수

인프런, 자바(Java) 알고리즘 문제풀이

HashMap, TreeSet(자료구조) - 0405. K번째 큰 수

---

🗒️ 문제

---

🎈 나의 풀이

	private static int solution(int n, int m, Integer[] arr) {
        ArrayList<Integer> list = new ArrayList<>();
        HashMap<Integer, Integer> dupCheck = new HashMap<>();

        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                for(int k=j+1; k<n; k++) {
                    int sum = arr[i] + arr[j] + arr[k];
                    if(!dupCheck.containsKey(sum)) {
                        dupCheck.put(sum, sum);
                        list.add(sum);
                    }
                }
            }
        }

        Collections.sort(list);
        Collections.reverse(list);

        if(list.size() < m) return -1;
        return list.get(m - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Integer[] arr = new Integer[n];

        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(n, m, arr));
    }

---

🖍️ 강의 풀이

    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;
        
		for(int x : Tset){
			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));
	}

---

💬 짚어가기

해당 문제는 발생 가능한 경우의 수를 중복 없이 찾는 문제이다.

나의 풀이의 경우 3중 반복문을 통해 3장의 카드를 뽑는 모든 경우의 수를 순회하였다.
Map 자료형의 변수를 두어 중복을 체크하였고, 중복되지 않은 조합의 경우 list에 저장하고
마지막으로 list을 내림차순으로 정렬하였다.

강의 풀이의 경우 TreeSet 자료구조를 사용했다. 이는 이진탐색트리(BinarySearchTree)의
형태로 데이터를 저장하여 중복이 없고, 자동으로 정렬된다.

☕️ 여담으로

처음 접근한 방식으로 카드셋을 먼저 내림차순으로 정렬하고, 이후 정렬된 카드셋을 3중 반복문으로
순회하며 모든 경우의 수를 조합하도록 설계하였다. 다음으로 중복되지 않은 조합만 list에 저장하여
최종적으로 list의 k-1 번째 index의 값을 반환하도록 구현했다.

결과는 오답 처리

list를 확인해보니 내 생각과는 달리 요소들이 정렬되어 있지 않았다. 정렬된 카드셋이라 할지라도
이후의 조합에서 이전의 조합보다 더 큰 조합이 발생할 수 있다는 사실을 알지 못했다..