[백준] 5052번 - 전화번호 목록

1차 시도 - 시간초과

# 전화번호 목록
import sys

T = int(sys.stdin.readline().rstrip()) # 테스트 케이스 개수
for _ in range(T):
    phone = list()
    N = int(sys.stdin.readline().rstrip()) # 전화번호 수
    for _ in range(N):
        phone.append(sys.stdin.readline().rstrip())
    phone.sort()
    check = 0
    for p in phone:
        for x in phone:
            if p in x and p != x:
                print("NO")
                check += 1
                break
    if check == 0:
        print("YES")

삼중 for문을 썼으니 당연히 시간초과

2차 시도 - 틀렸습니다

정렬을 했으니 이를 활용해보자는 생각을 하게 되었고, 현재 값과 바로 뒤의 값만 비교하면 되겠다는 생각을 하게 되었다.

# 전화번호 목록
import sys

def fcheck(phone):
    for i in range(len(phone)-1):
        if phone[i] in phone[i+1]:
            print("NO")
            return
    print("YES")


T = int(sys.stdin.readline().rstrip()) # 테스트 케이스 개수
for _ in range(T):
    phone = list()
    N = int(sys.stdin.readline().rstrip()) # 전화번호 수
    for _ in range(N):
        phone.append(int(sys.stdin.readline().rstrip()))
    phone.sort() # 전화번호 정렬하기
    phone = list(map(str,phone))
    fcheck(phone)

3차 시도 - 틀렸습니다

문제를 다시 읽어봤고 "접두어"를 놓쳤다는 것을 알게되었다.
3차 시도 전까지 시도했던 코드들은 모두 해당 값이 어디에 위치해있든 포함되어 있으면 일관성이 없다고 판단하도록 하였는데, 문제를 다시 읽어보니 접두어인 경우에만 "NO"를 출력해야 했다.

# 전화번호 목록
import sys

def fcheck(phone):
    for i in range(len(phone)-1):
        prefix = phone[i] # 접두어
        check = phone[i+1][:len(prefix)] # 접두어만 비교하기 위해 split
        if prefix == check: # 접두어가 동일한 경우 일관성이 없다고 판단
            print("NO")
            return
    print("YES")


T = int(sys.stdin.readline().rstrip()) # 테스트 케이스 개수
for _ in range(T):
    phone = list()
    N = int(sys.stdin.readline().rstrip()) # 전화번호 수
    for _ in range(N):
        phone.append(int(sys.stdin.readline().rstrip()))
    phone.sort() # 전화번호 정렬하기
    phone = list(map(str,phone)) # int형태로 정렬한 뒤 다시 문자열로 변환
    fcheck(phone)

최종 코드

# 전화번호 목록
import sys

def fcheck(phone):
    for i in range(len(phone)-1):
        prefix = phone[i] # 접두어
        check = phone[i+1][:len(prefix)] # 접두어만 비교하기 위해 split
        if prefix == check: # 접두어가 동일한 경우 일관성이 없다고 판단
            print("NO")
            return
    print("YES")


T = int(sys.stdin.readline().rstrip()) # 테스트 케이스 개수
for _ in range(T):
    phone = list()
    N = int(sys.stdin.readline().rstrip()) # 전화번호 수
    for _ in range(N):
        phone.append((sys.stdin.readline().rstrip()))
    phone.sort() # 전화번호 정렬하기
    fcheck(phone)

2차시도 이후 정렬을 잘못했다는 것을 알아차렸어야 했는데 빨리 풀려고 하다보니 생각이 꼬인 것 같다.
숫자를 오름차순으로 정렬한 상태에서는 뒤의 값을 비교해도 의미있는 결과가 도출되지 않는다. 우연히 테스트케이스는 맞아서 바로 발견하지 못했던 것 같다.

문제 오류 부분
['1','10','3','22','23','4','2','200']이 주어졌다고 가정했을 때

• 문제에서 원한 정렬 방법
  ['1', '10', '2', '200', '22', '23', '3', '4']
• 내가 했던 정렬 방법
  ['1','2','3','4','10','22','23','200']