Dictionaries and Hashmaps: Frequency Queries

Key-value 관계를 정의할 때 dictionary를 사용한다. 풀려고 하는 문제가 item들에 대한 정보를 모두 가지고 있어야 한다면 list 와 같은 자료형을 사용할 수 있겠으나 출현빈도와 같은 경우에는 dictionary 를 사용해 효율적으로 처리할 수 있다.

Problem

You are given $q$ queries. Each query is one of the form two integers described below:

• $(1, x)$: Insert $x$ in your data structure.
• $(2, y)$: Delete one occurence of $y$ from your data structure, if present.
• $(3, z)$: Check if any integer is present whose frequency is exactly $z$. If yes, print 1 else 0.

The queries are given in the form of a 2-D array queries of size $q$ where queries[i][0] contains the operation, and queries[i][1] contains the data element.

Let’s assume following queries are given:

queries = [(1,1), (2,2), (3,2), (1,1), (1,1), (2,1), (3,2)]

Output of this query is [0,1] from following operations:

1
2
3
4
5
6
7
8

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

Complete the freqQuery function. freqQuery has the following parameters:

• int queries[q][2]: a 2-d array of integers

It returns int[], the result of queries of type 3.

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def freqQuery(queries):
    query_dict = {}
    return_list = []

    for command, value in queries:
        if command == 1:
            val_count = query_dict.get(value, 0)
            val_count += 1
            query_dict[value] = val_count
        elif command == 2:
            val_count = query_dict.get(value, 0)
            val_count -= 1
            query_dict[value] = max(val_count, 0)
        elif command == 3:
            if value > len(query_dict):
                return_list.append(0)
                continue
            if value in query_dict.values():
                return_list.append(1)
            else:
                return_list.append(0)
        else:
            ValueError("Invalid Key")
                
    return return_list

Explanation

Python의 built-in Counter를 사용하는 방법도 있겠으나 이 문제에서는 list의 원소를 직접 관리할 필요는 없으므로 dict를 활용해 처리하였다. Operation 중 1과 2는 dict.get을 key가 없는 경우를 간단하게 처리해줄 수 있고 operation 3도 dict.values를 사용해 존재 유무를 쉽게 파악할 수 있다. 다만, 이 문제에서 10, 11번 테스트가 time limit에 대한 처리를 필요로 하므로 약간의 트릭이 필요하다. Operation 3일 때 if value in query_dict.values()에서 시간이 소요될 것임을 예상할 수 있다. 즉 가능하다면 이 operation을 수행하지 않는 것이 시간 단축에 도움이 될 것이다. 여기서는 간단하게 조회하려는 빈도수가 dictionary길이 전체보다 클 수는 없으므로 이 조건일 경우 continue를 통해 시간을 단축하였고 결과적으로 모든 테스트에 통과하였다.

Reference

• HackerRank