백준 - 1181 단어 정렬(Python)

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

1181번: 단어 정렬

문제

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

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

단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

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

출력

조건에 따라 정렬하여 단어들을 출력한다.

 

풀이

중복을 제거하고, 정렬 조건이 2개인 정렬 문제입니다. 리스트를 저장합니다. 이때, 리스트의 원소는 튜플로 받으며 첫번째 인자로 문자열의 길이를 받고 두번째로 문자열을 받습니다. 만약, 같은 튜플이 있으면, 리스트에 삽입을 하지 않습니다. 이후 soted 함수 의 key를 첫번째 인자, 두번째 인자 순으로 정렬을 해주면 풀이가 끝나게 됩니다.

 

N = int(input()) # N 입력

word_list = [] # 입력 문자열을 저장할 리스트

for i in range(N): # N 만큼 순회
    word = input() # 문자열 입력
    if (len(word), word) not in word_list: # 만약 해당하는 튜플이 리스트에 존제하지 않으면
        word_list.append((len(word),word)) # 튜플을 리스트에 저장

sorted_word_list = sorted(word_list,key=lambda x : (x[0],x[1])) # 길이와, 사전식으로 정렬

for i in range(len(sorted_word_list)): # 중복이 제거된 만큼 순회
    print(sorted_word_list[i][1]) # 출력

 

하지만 이것보다 더 좋은 풀이 방법이 있습니다. 먼저 리스트에 문자열을 받은 후 set을 이용해 중복을 제거합니다.

이후에 일반 사전식 정렬을 한번 해주고, sorted(word_list,key=len)을 사용하게 되면 문자열의 길이 순으로 정렬이 완성되게 됩니다.

N = int(input()) # N 입력

word_list = [] # 문자열 리스트 생성

for i in range(N): # 문자열 입력
    word = input()
    word_list.append(word)

setList = set(word_list) # 중복 제거
word_list = list(setList) # 리스트로 변환
sorted_list = sorted(word_list) # 사전식 정렬
sorted_list = sorted(sorted_list,key=len) # 길이순 정렬

for item in sorted_list: # 출력
    print(item)