[백준 5052] 전화번호 목록 - python (solved.ac - 골드 4)

풀이

문제를 보았을때 알수있는 힌트

• 접두어인 경우가 없어야한다.

접두어라는 이야기는 문자열에서 사용하는 트라이(trie)를 이용하는 문제일 확률이 높다.

그렇기에 트라이를 이용한 방식으로 문제를 풀어보면 된다.

 

trie 란, 문자열에 특화된 자료구조인 트라이는 문자열 집합을 표현하는 트리 자료구조이며, 우리가 원하는 원소를 찾는 작업을 O(n)에 해결 할수있는 자료 구조이다. 

 

먼저 전화번호를 낱개로 받아와 배열에 저장시킨다.

tel=[]
for i in range(n):
	tel.append(list(map(int,input().strip())))
    
tel.sort(reverse=True)

이렇게 배열에 저장을 하면 [[9,1,1],[9,7,6,2,5,9,9,9][9,1,1,2,5,4,2,6]] 이렇게 저장이 된다.

이를 내림차순으로 정리를 한다. 내림차순으로 정리한 이유는 비교할 다음 배열을 보며 같은지 다른지를 판별하기 위해서다

 

result = False
for i in range(n-1): # 마지막은 비교 할 대상이 없기 때문에 n-1
	for j in range(len(tel[i])): # j는 배열에 낱개를 하나씩 가져온다.
		if tel[i+1][j]!=tel[i][j]: # 앞에 있는 배열과 다른지 비교
    		break
    	else: # 같은 경우
    		if len(tel[i+1])<=j+1: # 앞에 배열이 똑같게 끝이 났다면 일관성이 없다.
    			result=True
    	    	break
if result==True:
    print("NO")
else:
    print("YES")

정렬을 마친후에 선택한 배열과 이후 배열을 비교하여 다른 경우는 넘어가고 같은 경우는 계속 확인을 한다.

완전히 일치하는 경우 일관성이 없기 때문에 result를 True로 하여 결과값이 NO가 나오게 한다.

 

전체 코드

import sys
input= sys.stdin.readline

case = int(input())

for _ in range(case):
    n = int(input())
    tel=[]
    result = False
    for i in range(n):
        tel.append(list(map(int,input().strip())))
    tel.sort(reverse=True)
    for i in range(n-1): # 마지막은 비교 할 대상이 없기 때문에 n-1
        for j in range(len(tel[i])): # j는 배열에 낱개를 하나씩 가져온다.
            if tel[i+1][j]!=tel[i][j]: # 앞에 있는 배열과 다른지 비교
                break
            else: # 같은 경우
                if len(tel[i+1])<=j+1: # 앞에 배열이 똑같게 끝이 났다면 일관성이 없다.
                    result=True
                    break
    if result==True:
        print("NO")
    else:
        print("YES")

 

문자열의 접두사나 정렬해서 찾는 문제가 있다면 이런식으로 풀면 된다.

 

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon5052.py