알고리즘 #0006

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제에 따르면, 가장 적은 수의 귤 종류를 제거해야 한다.
• 먼저 아래의 [코드 1]처럼 코드를 작성한다.
• nCr = $n!\over(n-r)!$인 점에 착안하여 조합을 구하는 메서드를 정의하였다.
• [코드 1] 처음 작성한 코드 답안

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerines) {
        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int tangerine: tangerines) {
            if (!map.containsKey(tangerine)) {
                map.put(tangerine, 1);
            } else {
                map.replace(tangerine, map.get(tangerine) + 1);
            }
        }
        int count = 0;
        while (count < k) {
            count += getMaxValue(map)[1];
            map.remove(getMaxValue(map)[0]);
            answer++;
        }
        return answer;
    }
    private int[] getMaxValue(HashMap<Integer, Integer> map) {
        Iterator<Integer> keyIterator = map.keySet().iterator();
        int maxValue = 0;
        int newKey = 0;
        while(keyIterator.hasNext()) {
            Integer key = keyIterator.next();
            Integer value = map.get(key);
            if (maxValue < value) {
                maxValue = value;
                newKey = key;
            }
        }
        return new int[] {newKey, maxValue};
    }
}

2. 실행 결과

• 하지만, 아래의 [결과 1]에서처럼 시간 초과가 발생하였다.
• [결과 1]
  

II. 문제 분석

1. 시간 복잡도 계산

• 기존 [코드 1]의 getMaxValue()에서 반복문이 n번 실행되었을 때 solution()의 while문에서 n번 실행되므로 시간 복잡도는 O(n$^2$)이다.

2. 코드 수정

• 귤을 HashMap 자료구조에 필요한 데이터만 저장하고 Key-Value 쌍에서 Value 값을 기준으로 정렬하면 HashMap을 N번만 순회하면 된다.

---

• [코드 2]
  

3. 결과

• [결과 2]