BOJ 5052 전화번호 목록

https://www.acmicpc.net/problem/5052
시간 1초, 메모리 256MB
input :

• t(1 <= t <= 50)
• n(1 ≤ n ≤ 10000)

output :

• 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력

조건 :

• 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

---

각 단어의 길이에 대해서, 각 단어들을 저장해 놓고 찾게 하면 어떨까 생각했다.
입력받는 문자열의 수도 적고 해서 괜찮지 않을까 했는데. 각 문자열에 대해서 모든 길이의 경우를 따지는 것이 있어서 시간이 초과 되었다.

그러던 와중 찾은 것이 접두어가 동일한 문자열의 경우 이 문자열들을 오름차순 정렬 했을 때 바로 옆에 세트 메뉴 처럼 존재한다는 것이다.

3
911
97625999
91125426
예시의 경우
[911, 91125426, 97625999] 순서로 정렬이 되는데 이 때 0, 1 번째를 비교해서 찾아내면 된다.

그렇다면 어떻게 찾아낼 것인가?
두 문자열 중 길이가 짧은 번호가 긴 번호의 앞에 존재하는지 확인 하면 된다.
그리고 이를 슬라이싱을 통해서 찾았다.

    for idx in range(1, len(data)):
        long = data[idx - 1]
        short = data[idx]
        if len(short) > len(long):
            short, long = long, short

        if long[:len(short)] == short:
            flag = 0
            break

import sys

t = int(sys.stdin.readline())
for i in range(t):

    n = int(sys.stdin.readline())
    data = []
    flag = 1

    for j in range(n):
        data.append(sys.stdin.readline().strip())
    data.sort()

    for idx in range(1, len(data)):
        long = data[idx - 1]
        short = data[idx]
        if len(short) > len(long):
            short, long = long, short

        if long[:len(short)] == short:
            flag = 0
            break

    print("YES" if flag else "NO")