[BOJ] 단어정렬 (#1181)

 

문제 

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

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

 

입력 

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

 

 

출력 

 

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

 

 

나의 코드 

N = int(input())
array = []
new_array = []
for _ in range(N):
  word = input()
  array.append(word) # word를 삽입하는 array 만들기
  array = list(set(array)) # 중복 원소 제거
array.sort() # 알파벳 순서로 배열

# 문자열 길이 순으로 배열
for _ in range(len(array)):
  for i in range(len(array)-1):
    if len(array[i]) > len(array[i+1]):
      array[i],array[i+1] = array[i+1],array[i]

# 배열 내 원소 출력 
for i in array:
  print(i)

분석 > 처음에는 문제에 나온 순서대로 문자열 길이대로 배열을 하고 문자열의 길이가 같은 경우는 알파벳 순서로 다시 배열을 하려니까 문자열의 길이가 같은 경우 알파벳 순서로 어떻게 다시 배열을 해야 할지 난감했다. 그래서 구글링으로 다른 접근법을 찾아봤는데, 그냥 알파벳 순서로 배열을 한 다음, 문자열의 길이 순으로 배열하면 되는 것이었다. 그리고 그 접근법으로 푼 것이 이 코드인데, 시간 초과가 떴다. 

 

 

해설 코드

import sys

N = int(sys.stdin.readline())
array = []
for _ in range(N):
  array.append(sys.stdin.readline().strip()) # word를 삽입하는 array 만들기
array = list(set(array)) # 중복 원소 제거
array.sort() # 알파벳 순서로 배열

# 문자열 길이 순으로 배열
array.sort(key = len)

# 배열 내 원소 출력 
for i in array:
  print(i)

분석 > 이 코드를 통해 문자열의 길이 순으로 정렬해주는 혁명적인 코드를 알게 되었는데, 그것이 바로 array.sort(key = len) 이다. 나는 길이 순으로 비교를 할 때에 무조건 반복문으로 정렬해주었는데 이렇게 간단한 코드가 있다는 것을 알고 깜짝 놀랐었다. 그리고 sys.stdin.readlin()의 경우 출력 할 때 줄바꿈을 포함해서 출력하기 때문에, strip()을 추가해 주었다. 또 최종적으로 세로로 출력할 때에는 반복문으로 해당 원소를 출력하면 되는 것이다. 

 

 

1181번: 단어 정렬