Frequency Queries

def freqQuery(queries):
    respond = []
    dic = {}
    countDic = collections.defaultdict(list)

    for query in queries:
        qtype = query[0]
        value = query[1]

        if qtype == 1:
            if value in dic:
                prev = dic[value]
                dic[value] += 1
                countDic[prev].remove(value)
                countDic[dic[value]].append(value)
            else:
                dic[value] = 1
                countDic[1].append(value)
        elif qtype == 2:
            if value in dic:
                if dic[value] == 0:
                    continue
                prev = dic[value]
                dic[value] -= 1
                countDic[prev].remove(value)
                countDic[dic[value]].append(value)

        elif qtype == 3:
            found = countDic.get(value)
            respond.append(0 if found == None else 0 if len(found) == 0 else 1)

    return respond

 

3의 쿼리가 나왔을 경우 쿼리의 두번째 값인 해당 개수만큼 어느 숫자든 배열에 존재하는지 물어보는 문제이다. 예를 들면, [3 2]가 쿼리로 들어오면 같은 숫자가 2개 존재하는게 배열에 있는지 없는지 찾아내는 문제다.

 

그래서 카운팅 딕셔너리를 만들어서 매 쿼리마다 개수의 변동사항을 저장한 다음에 출력 쿼리(3)가 나왔을 경우 카운팅 딕셔너리에서 해당 키의 값을 출력만 하면 된다.

 

카운팅 하는 방법을 딕셔너리를 사용하지 않는다면 출력 쿼리마다 현재 배열의 처음부터 끝까지 돌면서 찾아야 하기 때문에 타임 아웃이 발생할 것을 예상 할 수 있다.

 

위의 코드에서 좀 더 최적화를 하면 카운팅 딕셔너리에 값으로 배열을 사용할 필요없이 개수만 저장해도 된다.

공간 최적화