[ baekjoon ] 1181. 단어 정렬

1181. 단어정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

길이가 짧은 것부터
길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

1. 위상 정렬 이용

주어진 문자열의 길이가 50을 넘지 않는다고 나와있어서 먼저 위상 정렬을 떠올랐다.
1. 50개의 배열을 생성해서, 각 문자열 길이에 해당하는 배열에 추가를 한다
2. 중복을 제거하기 위해 set -> list 과정을 거친다

import sys

input = sys.stdin.readline
n = int(input())
words = [[] for i in range(51)] # 길이 50으로 맞추자
for _ in range(n):
  word = input().strip() # strip() 안 하면 \n 덧붙여짐
  length = len(word)
  words[length].append(word)

for array in words:
  array = set(array)
  array = list(array)
  for i in sorted(array):
    print(i)

2. lambda식 이용

1. 입력받은 문자열만을 튜플로 만들어((문자열, 문자열길이)) 배열에 추가를 한다.
2. 중복을 제거하기 위해 set -> list 과정을 거친다
3. lambda식을 이용해, 먼저 문자열 길이 순으로 정렬하고 그 후 알파벳 기준으로 정렬

import sys

input = sys.stdin.readline
n = int(input())
words_tuple = []
for _ in range(n):
    word = input().strip()
    words_tuple.append((word, len(word))) # 튜플 이용

words_tuple = list(set(words_tuple)) #중복 삭제

#단어 숫자 정렬 > 단어 알파벳 정렬
words_tuple.sort(key = lambda word: (word[1], word[0]))

for word in words_tuple:
    print(word[0])

위상정렬을 이용해 소스코드를 작성할 때가 더 메모리용량이 작고, 시간도 적게 드는 것을 알 수 있다.