백준 - 전화번호 목록 / Gold 4 / 5052번 / Python

문제 📋

백준 - 전화번호 목록

풀이 📝

import sys
from collections import defaultdict


def solution(n, phone_nums):
    phone_dict = defaultdict(bool)

    for phone_num in phone_nums:
        phone_dict[phone_num] = True

    for phone_num in phone_nums:
        temp = ""
        for char in phone_num:
            temp += char
            if phone_dict[temp] and temp != phone_num:
                return "NO"
    return "YES"


t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    phone_nums = [sys.stdin.readline().rstrip() for _ in range(n)]

    print(solution(n, phone_nums))

어렵지 않은 문자열 문제이다.
다음과 같이 크게 2가지로 단계로 답을 찾았다.

1. 전화번호들을 딕셔너리에 등록
2. 접두어 파악

• 번호들을 순회하면서 하나의 번호에 대하여 앞에서부터 부분 문자열을 만들어 딕셔너리 조회.

고려할 점

• 시간 복잡도 측면에서 봤을 때 전화번호들을 O(N)으로 순회하고 테스트케이스 숫자 고려하더라도 최대 50만으로 이슈 없다.
• 메모리 제한이 256MB이기 때문에 부분 문자열을 슬라이싱으로 계속해서 복사하면 문제가 생길 수도 있다.
• 딕셔너리 대신 set을 쓰면 안 된다.
  문자열은 immutable 객체이기 때문에 set에서는 문자열 내용이 같아도 새로운 문자열 객체로 인식한다.
  따라서 문자열을 key로 하는 딕셔너리를 만들어야 한다.