👩‍💻🔠 [baekjoon] 5052번: 전화번호 목록

🖍️ solution

import sys

"""
[시간]
1) 15:20 ~ 16:00

[요약]
1) 주어진 전화번호 목록을 보고, 일관성이 여부 판단
    - 하나의 번호가 다른 번호의 접두어 X
    - 주어진 모든 번호에 동일하게 연락할 수 있어야 일관성 있다고 판단
[전략]
1) 전화번호 앞자리를 최우선 기준으로 정렬
    - 시간 제한 & 입력의 길이: 이중 루프 커버 불가능
    - 숫자처럼 생긴 '문자열'을 정렬, 길이와 관계 없이 자리수에 채워진 숫자가 비슷한 번호끼리 뭉침
        => 그래서 굳이 이중 루프를 이용해 전체를 탐색할 필요가 없음
        => 애초에 비슷한 것끼리 뭉쳐 있는 상태라서, local optimal ~ global optimal 기대 가능
        => 다만, 길이를 기준으로 정렬한게 아니라서, 슬라이싱 기준을 길이로 정해 줘야 한다.
"""
for _ in range(int(sys.stdin.readline())):
    checker, result = False, 'YES'
    num_list = [sys.stdin.readline().rstrip() for _ in range(int(sys.stdin.readline()))]
    num_list.sort()

    for i in range(0, len(num_list)-1):
        if num_list[i][:min(len(num_list[i]), len(num_list[i+1]))] == num_list[i+1][:min(len(num_list[i]), len(num_list[i+1]))]:
            print('NO')
            checker = True
            break

    if not checker:
        print(result)

💡 idea

• 1) 전화번호 앞자리를 최우선 기준으로 정렬
  • 시간 제한 & 입력의 길이: 이중 루프 커버 불가능
  • 숫자처럼 생긴 ‘문자열’을 정렬, 길이와 관계 없이 자리수에 채워진 숫자가 비슷한 번호끼리 뭉침
    • 그래서 굳이 이중 루프를 이용해 전체를 탐색할 필요가 없음
    • 애초에 비슷한 것끼리 뭉쳐 있는 상태라서, local optimal ~ global optimal 기대 가능
    • 다만, 길이를 기준으로 정렬한게 아니라서, 슬라이싱 기준을 길이로 정해 줘야 한다.

무지성으로 사용하던 정렬에 대해서 다시 한 번 생각하게 된 계기가 된 문제다. 필자는 처음 이 문제를 풀이할 때, 정렬하는 대상을 숫자라고 오인해 key=len 을 사용해 정렬을 했다. 이렇게 하면 문제가 무조건 이중 루프를 사용해야만 한다. 그러면 시간 초과에 걸리기 때문에 문제를 해결할 수 없다.

문제를 틀리고 나서 생각을 해보니, 정렬하는 대상은 실제 숫자가 아니라 ‘숫자처럼 생긴’ 문자열이다. 이 점을 잘 이용하면, 앞자리의 숫자가 비슷한 것끼리 뭉치게 정렬을 해줄 수 있다. 그렇다면 굳이 이중루프를 사용할 필요가 사라지고, 바로 옆 원소와 대조만 해도 global optimal을 기대해볼 수 있게 된다. 하지만 길이를 기준으로 문자열을 정렬한 것은 아니기 때문에 슬라이싱 기준을 min()을 이용해 더 짧은 문자열로 삼아줘야 한다.