접근 방법
- 숫자 갯수가 작은 순으로 정렬
- 문자열로 변환
- 정렬된 순서로 특정 전화번호와 다른 전화번호들을 비교(특정 전화번호 갯수까지 잘라서 그부분만 비교)
- 같을 경우 YES 출력 후 종료
- 다를 경우 3번 반복
실패 코드(시간초과)
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
phone_list = [int(sys.stdin.readline()) for i in range(n)]
phone_list.sort()
phone_list = list(map(str, phone_list))
index = 0
check = 0
while index < n - 1:
if check:
break
phone_num = phone_list[index]
phone_len = len(phone_num)
tmp = index + 1
while tmp < n - 1:
if phone_num == phone_list[tmp][:phone_len]:
print("NO")
check = 1
break
else:
tmp += 1
index += 1
if check == 0:
print("YES")
다른 사람들이 푼 것을 보니 정렬을 하면 바로 옆 문자열만 비교하면 됐던 문제다. (위 실패코드에서 두번째 while문 삭제)
정답코드 1
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
phone_list = [sys.stdin.readline().strip() for i in range(n)]
phone_list.sort()
index = 0
check = 0
while index < n - 1:
phone_num = phone_list[index]
phone_len = len(phone_num)
if phone_num == phone_list[index + 1][:phone_len]:
print("NO")
check = 1
break
else:
index += 1
if check == 0:
print("YES")
또한 이 문제는 Trie로 풀 수도 있다고 한다.
추후 업로드 예정
정답 코드 2
'코딩테스트 > Python' 카테고리의 다른 글
[python 백준 1439] 뒤집기 (0) | 2023.01.25 |
---|---|
[python 백준 9358] 순열 접기 게임 (0) | 2023.01.17 |
[python 백준 13904] 과제 (0) | 2023.01.15 |
[python 백준 1931] 회의실 배정 (1) | 2023.01.14 |
[python 백준 1946] 신입 사원 (0) | 2023.01.13 |