[BOJ 5052] 전화번호 목록 (Python)
[BOJ 5052] 전화번호 목록 (Python)
풀이
처음에는 시간 초과가 발생하지 않을 것으로 예상하여 포인터 2개를 활용하여 비교 기준이 되는 번호가 비교대상 번호의 접두어가 되는지 판단하는 방식으로 접근하였다. 하지만, 시간 초과가 발생하였다...
문제의 포인트는 오름차순 정렬이다. 전화번호 목록에서 비교 번호가 바로 뒤에 있는 번호의 접두어인지만 확인하면 된다. 이는 정렬이 되었기에 해당 로직으로 전화번호 목록의 일관성을 파악할 수 있다.
트라이와 해시 자료구조를 이용한 풀이도 있다고 한다.
코드
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
phone_num = [input().rstrip() for _ in range(N)]
# 전화번호 목록 오름차순 정렬
phone_num.sort()
flag = False
for i in range(N - 1):
# 비교 번호가 바로 뒤에 있는 번호의 접두어인 경우인지 확인
# --> 정렬되었기에 이 조건만으로도 일관성을 판단할 수 있다.
if phone_num[i] == phone_num[i + 1][0:len(phone_num[i])]:
flag = True
break
if flag:
print('NO')
else:
print('YES')
Author And Source
이 문제에 관하여([BOJ 5052] 전화번호 목록 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kimdukbae/BOJ-5052-전화번호-목록-Python
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
phone_num = [input().rstrip() for _ in range(N)]
# 전화번호 목록 오름차순 정렬
phone_num.sort()
flag = False
for i in range(N - 1):
# 비교 번호가 바로 뒤에 있는 번호의 접두어인 경우인지 확인
# --> 정렬되었기에 이 조건만으로도 일관성을 판단할 수 있다.
if phone_num[i] == phone_num[i + 1][0:len(phone_num[i])]:
flag = True
break
if flag:
print('NO')
else:
print('YES')
Author And Source
이 문제에 관하여([BOJ 5052] 전화번호 목록 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimdukbae/BOJ-5052-전화번호-목록-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)