[HackerRank] Frequency Queries #파이썬 #Inverted #Index

https://www.hackerrank.com/challenges/frequency-queries/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps 

Frequency Queries | HackerRank

You are given q queries. Each query is 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.

1 x면 리스트에 숫자 x를 넣고, 2 y면 숫자 y의 빈도를 하나 줄이고, 3 z면 리스트에 빈도가 z인 요소를 찾아 있으면 1, 없으면 0을 output에 포함합니다.

물론... 문제에서 시키는대로 리스트를 이용하여 구성하면 시간초과가 발생합니다. 우리가 리스트에서 필요한 정보는 빈도 뿐이므로, 빈도만을 기록하는 딕셔너리를 구성할 수 있습니다. 이 경우, 순회하지 않고도 빈도를 구할 수 있기 때문에 문제를 풀 수 있을 것 같지만, 마지막 테스트 케이스에서 시간초과가 발생합니다. 3: 확인 과정에서 원하는 빈도 값을 찾아 딕셔너리 순회가 필요하기 때문입니다. 이때 사용할 수 있는 개념이 Inverted Index입니다.

https://ko.wikipedia.org/wiki/%EC%97%AD%EC%83%89%EC%9D%B8

역색인

위키백과, 우리 모두의 백과사전.

컴퓨터 과학에서 역색인, 역 인덱스(inverted index), 역 파일(inverted file)은 낱말이나 숫자와 같은 내용물로부터의 매핑 정보를 데이터베이스 파일의 특정 지점이나 문서 또는 문서 집합 안에 저장하는 색인 데이터 구조이다. 역색인의 목적은 문서가 데이터베이스에 추가될 때 늘어나는 처리를 위해 빠른 전문 검색을 가능케 하는 것이다. 역 파일은 색인이 아닌, 데이터베이스 파일 그 자체를 가리킬 수도 있다. 문서 검색 시스템에 쓰이는 가장 대중적인 데이터 구조로서[1], 이를테면 검색 엔진과 같은 대규모에 쓰인다. 일부 중요한 일반 목적 메인프레임 기반 데이터베이스 관리 시스템들은 역색인 구조를 사용해 왔으며 아다바스, 데이터콤/DB, 모델 204 등이 있다.

역색인은 두 가지 주된 종류가 있다: 레코드 단위의 역색인, 낱말 단위의 역색인[2]

간단히 말해서 현재 dict[숫자] = 빈도로 나타내고 있다면, dict[빈도] = [숫자1, 숫자2, ...] 또한 유지하는 편이 2: 삭제, 3: 확인을 더 빠르게 만들어줍니다.

# ...
from collections import defaultdict

def freqQuery(queries):
    output = []
    count = defaultdict(int)
    invertedCount = defaultdict(list)
    
    for q, n in queries:
        if q == 1:
            if count[n] == 0:
                invertedCount[1].append(n)
                count[n] = 1
                continue
            
            invertedCount[ count[n] ].remove(n)
            invertedCount[ count[n] + 1 ].append(n)
            count[n] += 1
            
        elif q == 2:
            if count[n] == 0:
                continue
            
            invertedCount[ count[n] ].remove(n)
            if count[n] > 1:
                invertedCount[ count[n] - 1 ].append(n)
            count[n] -= 1
                
        else:
            output.append(int(len(invertedCount[n]) > 0))
            
    return output
    
# ...