5022번 - 전화번호 목록

**문제

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

**오류 코드 (Time Limit)

from sys import stdin

numTestCase = int(stdin.readline().strip())
tot = []

for _ in range(numTestCase):
    cntPhone = int(stdin.readline().strip())
    phoneNum = []
    for _ in range(cntPhone):
        number = stdin.readline().strip()
        phoneNum.append(number)
    tot.append(phoneNum)

for ii in tot:
    min = 10
    okay = True
    for i in ii:
        if len(i) > min and i[:min] in ii:
            okay = False
            print('NO')

        if len(i) < min:
            min = len(i)

    if okay :
        print('YES')

 

 

리스트의 반복문을 모두 돌게된다면 타임아웃!

 

 

 

** 키 포인트

문제에서 말하는 일관성을 가진다 == 전화번호 맨 앞부분이 기존에 있는 전화번호입니다.

따라서 우리는 맨 앞 부분을 체크하기 편하게, 전화번호를 정렬할겁니다.

문자열로 입력받은 값을 정렬하면,

'사전식'으로 정렬 되어서,

각각의 입력값과 가장 유사한 값들이 바로 옆에 오게 됩니다.

입력 예시 값이며,

 

 

 

 

위의 결과는, 각각의 테스트 케이스별 전화번호를 리스트로 저장한 것입니다.

911과 91125426이 붙어있고,

113과 12340, 이후 123440과 12345모두 바로 옆에 붙어있다.

사전식으로 정렬되어서 그렇다.

 

그래서 우리는,

바로 옆에 있는것들의 앞부분을 체크할 것이다.

 

911과 91125426, 91125426과 97625999를 체크한다는 뜻이다.

 

 

**정답

from sys import stdin

numTestCase = int(stdin.readline().strip())
tot = []

for _ in range(numTestCase):
    cntPhone = int(stdin.readline().strip())
    phoneNum = []
    for _ in range(cntPhone):
        number = stdin.readline().strip()
        phoneNum.append(number)
    phoneNum.sort()
    tot.append(phoneNum)


for ii in tot:
    okay = True
    for i in range(len(ii)-1):
        if ii[i] == ii[i+1][:len(ii[i])]:
            okay = False
            print('NO')
            break
    if okay == True:
        print('YES')

 

 

 

**결과