HackerRank : Frequency Queries

문제 링크

The problem link : Frequency Queries

문제 요약

2차원 쿼리가 주어집니다. 이때 쿼리가 가진 값의 의미는 다음과 같습니다.

• 1 x : x를 저장
• 2 y : y값이 저장되어있을 경우, 제거
• 3 z : 빈도수(=누적된 개수)가 z인 값이 있을 경우, 1을 출력하고 그렇지 않을 경우 0을 출력

예시 코드는 다음과 같습니다.

Operation   Array   Output
(1,1)       [1]
(2,2)       [1]
(3,2)                   0
(1,1)       [1,1]
(1,1)       [1,1,1]
(2,1)       [1,1]
(3,2)                   1

문제 풀이

핵심 코드는 다음과 같습니다.

    static List<Integer> freqQuery(List<List<Integer>> queries) {
        HashMap<Integer, Integer> hm = new HashMap<>(); // 0
        List<Integer> ans = new ArrayList<>(); // 1
        int arr[] = new int[queries.size() + 1]; // 2
        int key, value, current; // 3
        for(List<Integer> query : queries){ 
            key = query.get(0);
            value = query.get(1);
            current = hm.getOrDefault(value, 0);
            switch (key) {
                case 1:
                    hm.put(value, current+1);
                    arr[current]--;
                    arr[current+1]++;
                    break;
                case 2:
                    if(current > 0){
                        hm.put(value, current-1);
                        arr[current]--;
                        arr[current-1]++;
                    }
                    break;
                case 3:
                    if (value > queries.size()) ans.add(0); // 4
                    else if(arr[value] != 0) ans.add(1);
                    else ans.add(0);
                    break;
            }
        }
        return ans;
    }

0. hm은 입력된 값과 해당 값의 빈도수를 저장할 hashMap입니다.
1. ans는 정답을 저장할 배열입니다.
2. arr는 빈도수(=누적된 개수)를 저장할 배열입니다. hashMap에 저장된 특정 value(=빈도수)를 가져오려면 hashMap에서 제공하는 containsValue를 사용하면 되지만, 이럴경우 시간 복잡도는 O(n)이 되므로, 1 <= queries[i][1] <= 10^9의 조건에서 Time Out이 발생할 수 있습니다. 때문에 빈도수를 O(1)의 시간 복잡도로 조회하기 위해 별도의 배열을 선언합니다. 추가로, 배열의 사이즈가 queries.size()+1인 이유는 최대한으로 누적될 수 있는 빈도수는 queries.size()+1이기 떄문입니다.
3. key는 queries의 명령문, value는 명령문의 주체가 될 숫자 (hashMap의 key값이 됨), current는 명령문의 주체가 될 숫자의 빈도수 입니다. (hashMap의 value이자 arr에 저장될 빈도수)
4. 나머지 코드는 순차적으로 읽어나가면 이해하기 쉽지만, 이 부분이 핵심입니다. 해당 코드를 간과할 경우 테스트 케이스에서 Runtime Out이 발생할 수 있습니다. 만약, value의 값이 queries.size()보다 클 경우, arr의 Index를 벗어난 값을 조회하게 됩니다. 해당 경우에 대한 예외를 처리해야하므로 4번의 코드를 추가해줍니다.

시간 복잡도

O(n)입니다.