[Python] 백준 1181번_단어 정렬

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

1181번: 단어 정렬

 

• 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬
  • 1. 길이가 짧은 것부터
  • 1. 길이가 같으면 사전 순으로

• 입력
  • 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 20,000)
  • 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어짐
  • 주어지는 문자열의 길이는 50을 넘지 않음
• 출력
  • 조건에 따라 정렬하여 단어들을 출력
  • 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력
• 시간 제한: 2초
• 메모리 제한: 256 MB

 

"""
입출력 예시)

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

    -> i
       im
       it
       no
       but
       more
       wait
       wont
       yours
       cannot
       hesitate
"""

 

 

## 의사코드 ##

# 길이가 짧은 것부터 출력 -> 길이를 우선순위로 우선순위 큐
# heapq.heappush(heap, (len(s), s)) # (문자의 길이, 문자)

# 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력
# -> answer라는 리스트를 생성하고, heappop한 문자를 answer에 저장
# if 문자 in answer: continue

 

 

 

통과한 코드

 

import heapq
n = int(input())
heap = [] # 우선순위 큐 
answer = []
for i in range(n):
    s = str(input())
    heapq.heappush(heap, (len(s), s)) # (문자의 길이, 문자)

# 우선순위 큐에서 데이터 꺼내기
while heap:
    len_temp, temp = heapq.heappop(heap)
    # 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력
    if temp in answer:
        continue 
    answer.append(temp)
    print(temp)

-> 문자의 길이를 우선순위로 해서 우선순위 큐인 heapq 활용

 

 

 

다른 풀이

 

import sys

n = int(sys.stdin.readline())
lst = []

for i in range(n):
    lst.append(sys.stdin.readline().strip())
set_lst = set(lst)
lst = list(set_lst)
lst.sort()
lst.sort(key = len)

for i in lst:
    print(i)

-> set()으로 중복 제거 후, sort() 함수의 key를 len으로 설정해서 문자의 길이를 기준으로 정렬

 

 

 

 

 

참고)

 

https://velog.io/@1204jh/1181

[Python / 파이썬] 백준 1181번