[백준][문자열] 전화번호 목록

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

내가 작성한 코드

import sys

def print_answer(phone):
    dic = dict()
    for num in phone:
        if is_prefix(dic, num):
            print("NO")
            return
    print("YES")

def is_prefix(dic, num):
    crnt = dic
    is_prefix = True

    for c in num:
        if c not in crnt:
            is_prefix = False
            crnt[c] = dict()
        crnt = crnt[c]
        if "word" in crnt:
            return is_prefix
    crnt["word"] = True
    return is_prefix


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

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

• trie 이용
• dict에 key로 char 하나씩 들어가므로, "word"로 워드가 완성됨을 나타냄
• 자꾸 타임아웃나서 뭔가 했더니, 백준은 input으로 받으면 너무 느린 듯하다
  • sys.stdin.readline().rstrip()

 

다른 사람이 작성한 코드

import sys
r = sys.stdin.readline

def solve(book):
    for p1, p2 in zip(book, book[1:]):
        if p2.startswith(p1):
            return False      
    return True

T = int(r())
for _ in range(T):
    N = int(r())
    flag = True
    book = []
    for _ in range(N):
        book.append(r().strip())

    book.sort()
    if solve(book):
        print("YES")
    else:
        print("NO")

• trie 이용하지 않고 prefix를 포함하는지 확인하는 방법
• sort 후 n-1개 비교

 

기억해야할 것

• zip
  • 두 리스트의 원소를 각각 쌍으로 만들어줌
  • zip(arr, arr[1:]) -> arr를 인접한 두 pair 생성
• startswith으로 prefix 확인 가능
• sorting이 사전순이므로, 길이에 상관없이 앞에서부터 비슷한 값으로 정렬됨