[HackerRank] Contacts (Python)

1.문제

https://www.hackerrank.com/challenges/contacts/problem

 

2.풀이

처음에 정직하게 구현으로 풀다가 time limit exceeded 나서 실패..

단순해 보이지만 Time Complexity를 신경써서 풀어야하는 문제이다.

def contacts(queries):
    answer = []
    arr = []

    for i in range(len(queries)):
        command = queries[i][0]
        if command == 'add':
            data = queries[i][1]
            arr.append(data)
        else:
            target = queries[i][1]
            cnt = 0
            for word in arr:
                if (word[:len(target)] == target):
                    cnt+=1
            answer.append(cnt)
    return answer

 

 

3.코드

defaultdict 를 사용한 풀이.

모든 prefix 경우의 수를 생성하여 카운트를 미리 저장한다.

dict와 defaultdict 의 차이는

- dict[key] => value 가 존재하지 않으면 에러 반환

- defaultdict[key] => value 가 존재하지 않으면 default 값 반환.

예를들어 defaultdict(int) 라고 하면 value 가 존재하지 않을 경우 0을 반환한다.

 

from collections import defaultdict

def contacts(queries):
    prefix_count = defaultdict(int)
    answer = []

    for command, value in queries:
        if command == "add":
            # 문자열의 모든 접두사를 생성하며 카운트 증가
            for i in range(1, len(value) + 1):
                prefix_count[value[:i]] += 1
        elif command == "find":
            # 접두사가 있는 경우 카운트 반환
            answer.append(prefix_count[value])

    return answer