[알고리즘] 단어 정렬 - 정렬

문제 링크

 

단어 정렬 : https://www.acmicpc.net/problem/1181

 

 

문제탐색

기본 원리 탐색

주어진 문제는 N개의 알파벳을 특정 조건에 따라 정렬하는 것입니다.
조건은 다음과 같습니다:

1. 길이가 짧은 순서로 정렬
2. 길이가 같다면 사전순으로 정렬
3. 또한, 중복된 단어는 하나만 남기고 제거해야 합니다.

정렬 기준이 길이와 사전순 두 가지로 명확히 나뉘므로,
각 단어를 [길이, 단어] 형태로 묶은 뒤 Python의 sorted 함수 기본값을 이용하면 해결할 수 있습니다.
단, 중복 제거를 위한 추가 작업이 필요하므로 이를 고려해 풀이를 설계해야 합니다.

 

 

시간복잡도와 알고리즘

 

• 시간 제한: 2초
  Python에서 약 2억 번의 연산이 가능하다고 가정합니다.
• 단어 수: 최대 20,000개
  시간 복잡도가 O(n²)인 알고리즘은 약 4억 회 이상의 연산이 필요하므로 비효율적입니다.

 

 

=>O(n log n) 복잡도를 가지는 Python의 sorted함수를 사용하는 방향으로 구현합니다.

 

코드설계하기

1. 각 단어를 입력받아 단어의 길이와 함께 튜플 형태로 리스트에 저장합니다.
2. set 함수를 사용해 중복된 단어를 제거합니다.
3. sorted 함수를 이용해 길이 기준으로 우선 정렬하고, 같은 길이의 단어는 사전순으로 정렬합니다.
4. 정렬된 리스트에서 단어만 출력합니다.

 

시도회차 수정사항

 

 

정답코드

n=int(input())

words=[]

for x in range(n):
    word = input()
    wordLen = len(word) #단어 길이 구하기
    words.append((wordLen,word))

for x in sorted(list(set(words))): #중복제거 및 정렬
    print(x[1]) #단어 출력