boj 5052 : 전화번호 목록

문제 주소: https://www.acmicpc.net/problem/5052

난이도: gold 4

1.문제설명

• 전화번호 목록이 주어진다.
• 전화기가 특이해서 전화번호를 누르다 완성되지 않아도 지금까지 입력된 값이 전화번호부에 있으면 전화가 걸린다.
• 예를들어 911이 있고, 김경식 91-1-3972-9271면 김경식한테 전화를 못건다. -> 일관성 없음
• 전화번호 목록이 주어졌을때 이 목록이 일관성 있는지 없는지 출력한다

2.문제해결 아이디어.

• 그냥 싹다 비교해보자
  • 이중 for문 피벗하나 잡고 뒤의 원소와 전체 비교 -> O(n^2)으로 시간초과 발생
• 입력받은 '문자열'을 정렬해보자 -> 정렬방식 사전식 오름차순
• 따라서 바로 뒤에있는 문자와 비교만하면됨

3.문제접근법

def solve():
    n = int(input())
    phone_list = []
    for i in range(n):
        phone_list.append(input().rstrip()) #rstrip안해주면 틀린다
    phone_list.sort() #정렬을 하냐 안하냐 아이디어가 중요
    for i in range(len(phone_list)-1):
        if phone_list[i] in phone_list[i+1][:len(phone_list[i])]:
            return print("NO")
    return print("YES")

4.특별히 참고할 사항

• 문자열 정렬의 결과는 사전순!

5.코드구현

import sys
input = sys.stdin.readline
t = int(input())
def solve():
    n = int(input())
    phone_list = []
    for i in range(n):
        phone_list.append(input().rstrip())
    phone_list.sort()
    for i in range(len(phone_list)-1):
        if phone_list[i] in phone_list[i+1][:len(phone_list[i])]:
            return print("NO")
    return print("YES")

for _ in range(t):
    solve()