[BOJ/PYTHON] 5052. 전화번호 목록

백준 문제 링크: https://www.acmicpc.net/problem/5052

문제 요약

주어진 전화번호 목록이 일관성이 있는지 없는지 구하기

일관성 있는 번호: 한 번호가 다른 번호의 접두어인 경우가 있으면 안 됨

핵심 아이디어

입력을 문자열로 받아서 정렬하면 숫자 크기와 상관 없이 사전순으로 정렬되기 때문에 맨 앞부터 순서대로 정렬된다. 정렬을 하고 시작하기 때문에 바로 다음 것과 비교하면 된다.

i번째 번호를 기준으로 삼았을 때, i+1번째 번호를 i번째 번호 길이까지만 보고, 둘이 동일하면 일관성 없는 것으로 보면 된다.

테스트 케이스 중 하나인 911, 91125426로 예시를 들어보자면 i번째 번호인 911을 기준으로 본다. 911의 길이는 3이다. 91125426을 앞 3개까지만 보면 911로 동일하다. 이러면 91125426을 입력하는 도중, 911까지만 입력했는데 긴급전화가 걸려버리기 때문에 일관성이 없다고 할 수 있다.

모든 경우를 다 봤는데도 일관성이 없는 케이스가 발견된 적 없으면 YES를 출력하면 된다.

풀이

# gold4-5052. 전화번호 목록

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    phone_numbers = [list(input().rstrip()) for _ in range(n)]

    has_consistency = True
    phone_numbers.sort()
    for i in range(n - 1):
        number_i_len = len(phone_numbers[i]) 
        # i+1번째 번호를 i번째의 길이까지 봤을 때 i번째 번호랑 동일하면 일관성 없는 것
        if phone_numbers[i] == phone_numbers[i + 1][:number_i_len]:
            has_consistency = False
            print("NO")
            break
    if has_consistency: print("YES")

실행 시간

메모리 33300KB, 시간 312ms (python3)