[Python] 5052번: 전화번호 목록

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

5052번: 전화번호 목록

시간 제한: 1초

메모리 제한: 256mb

<문제 풀이전 나의 생각>**************************************************

컴퓨터알고리즘 수업때 들었던 허프만 압축이 생각이 나네요 그때 참 신기했었는데 이걸 내가 풀게 될줄이야

허프만 압축처럼 트리 형태로도 풀수 있을것 같고

혹은 순열(permitation)을 활용해서 풀수도 있을것 같다.(이건 좀 비효율 적일듯)

재미있겠군 후후

 

 

<문제 푸는중 고민>**********************************************************

허프만 압축: 내가 한번 사용한 문자열 조합이 이후에 등장하는 것의 접두부가 되면 안됨

머리가 아프네 이참에 힙(우선순위 큐)구조를 정복하는게 좋을것 같다.

못풀겠네 트라이 알고리즘 공부하고 와야하나

그냥 무지성 비교 해볼까... 10^8승이라 시간복잡도가 간당간당할텐데...

import sys

T = int(sys.stdin.readline())

def check():
    for i in range(len(arr)-1):
        if arr[i] == arr[i+1][0:len(arr[i])]:
            print('NO')
            return
    print('YES')
    
for _ in range(T):
    N = int(sys.stdin.readline())
    arr = [sys.stdin.readline().strip() for __ in range(N)]
    arr.sort()
    check()

 

 

<문제를 풀고난뒤 후기>*********************************************************

우선 트라이(문자열 빠르게 찾는법)을 사용하지는 않았다. 그냥 단순하게 구현으로 해결했다.

또 YES를 Yes라고 잘못 적는바람에 맞왜틀을 하였다.

또 함수를 사용하므로써 내가 원할때 return 해버리면 끝낼수 있다는 장점을 또 상기하게 된다.

 

알게된점: heapq 모듈 안의 heappop(리스트명) heappush(리스트명, 넣고싶은것), heapify(리스트명) --> 사용시 최소힙구조 변환함

 

또한 최소힙만을 기본적으로 지원하기에 최대힙을 만들때는 요소를 정수가 아닌 (-정수, 정수) 형태로 넣은뒤 리스트[0][1]을 찾는 식으로 힙 구조를 만들면 된다. (튜플 앞에 원소인 -정수를 기준으로 최소힙을 만드는데, 이때 가장 작은것은 절대값이 가장 크다는 것과 같은 의미이기 때문이다.)

 

from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:    #아래는 힙의 원소구조를 단일정수에서 튜플형태로 변환하는 과정이다.
  heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heappop(heap)[1])  # index 1