[Python] 정렬 - 5052. 전화번호 목록(골4) / 관련성 순 정렬

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

5052번: 전화번호 목록

---

2. 핵심 아이디어

2-1) 정렬의 순서

처음에는 정렬의 순서를 문자열 길이로 생각하였다.

짧은 순대로 prefix의 가능성이 있는 뒤에 것과 대조해보면 될 것이라는 단순한 생각에.. 

 

그러나, 결국 본 문제는 다른 전화번호가 타 전화번호의 prefix가 되는지, 관련성을 묻는 문제이기에

전화번호를 기준으로 정렬을 하게 되면 결국 유사한 번호 순인 사전 순으로 정렬되게 된다.

 

따라서 모든 전화번호 쌍을 대조하는 것이 아닌

가장 관련성이 높은 인접한 전화번호(바로 뒤의 전화번호)만 비교해주면 되는 문제였다.

 

2-2) 트라이 자료구조

문자열 탐색에 최적화된 자료구조라고 한다. 이번 문제를 통해 처음 접하게 되는 만큼

링크 첨부로 대체

 

[자료구조] 트라이 (Trie)

---

3. 코드

k= int(input())

for _ in range(k):
    n= int(input())
    phone=[]
    for _ in range(n):
      number=input()
      phone.append(number)

    phone.sort()

    flag=0
    for i in range(n-1):
      number=phone[i]
      n_len= len(number)
      
      #뒤에 것하고만 비교
      if number == phone[i+1][:n_len]:
        print('NO')
        flag=1
        break

    if flag==0:
      print('YES')

---

4.배운 점

정렬을 하기 전에 어떤 것을 기준으로 문제를 접근해야 하는지 떠올리자.

관련성을 기준으로 정렬할 때엔 모든 요소 쌍을 검토할 필요가 없는 경우도 존재