(Python) - 백준(BOJ) 5052번 : 전화번호 목록 답

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

문자열을 다루는 문제였습니다.

 

풀이방법

 문자열을 사전순으로 정렬한 후 i+1번쨰에 있는 문자열에서 i가 있는 것을 확인만 한다면 O(n)만에 일관성 여부를 검사할 수 있습니다. 마지막으로 접두사의 의미를 정확히 알아야합니다.

만약 전화번호 목록에 211, 11211 이런식으로 있다면 11211에 211이 포함이 되어있음에도 접두사가 아니므로 일관성이 있습니다. YES를 출력해야하나 단순히 해당 문자열을 찾았다고 NO를 출력한다면 100%에서 틀리는 쓴 맛을 볼 수 있습니다. 전화번호 목록 i+1번째 문자열의 왼쪽 처음 문자부터 시작해 전화번호 목록 i번째 문자열의 길이만큼 slicing한 후 i와 비교해 일관성 여부를 판단하게 되면 맞을 수 있습니다.

 

 또한, input()으로 입력을 받으면 시간초과가 나기 때문에 readline()으로 입력을 받는 것이 좋습니다.

동작차이를 간단히 설명하자면 다음과 같습니다.

파이썬은 동적변수라지만 변수의 형태를 저장하기 위해서 input()메소드 내에서 가공을 해야 합니다.
raw_input()은 문자열을 반환하고 input()은 raw_input()을 evaluate한 결과를 반환합니다. 따라서 동작이 더 느립니다.

참고) raw_input()은 문자열만을 받는 input

sys.stdin.readline()은 한 줄의 문자열을 반환하는데 이를 출력해보면 ["12\n","123\n"...]식으로 되어있기 때문에 strip()함수를 사용해 escape 문자를 지워준 것입니다.

 

Code

import sys
def findPreffix(phoneBook):
    for i in range(len(phoneBook)-1):
        if phoneBook[i] == phoneBook[i+1][0:len(phoneBook[i])]:
            return "NO"
    return "YES"

t = int(input())
while t:
    t-=1
    phoneBook = []
    n = int(input())
    for i in range(n):
        phoneBook.append(sys.stdin.readline().strip())
    phoneBook.sort()
    print(findPreffix(phoneBook))