[백준 / python] 1181번 단어 정렬

오늘은 정렬 알고리즘이 필요한 백준 1181번 문제, 단어 정렬을 풀어보겠습니다!

 

< 문제 확인 >

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

---

📌 문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

주어진 단어들을 길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬하고,

중복된 단어는 하나만 남기고 출력하는 것.

 

이 문제를 해결하기 위해서는 입력받은 정보에서 중복되는 값을 제거하고,

중복이 제거된 집합 형태의 단어들을 리스트로 변환 후 길이와 사전(알파벳) 순으로 정렬해야 한다.

 

정렬과 관련된 여러 아이디어 중에서 파이썬 내장 정렬 함수인 Timsort를 사용할 수 있을 것이다.

 

그리고 이번에는 함수를 선언해서 시도해보기로했다!

 

✔️ 가능한 시간복잡도

N이 최대 20,000이므로, O(Nlog⁡N) 시간 복잡도를 가지는 정렬 알고리즘을 사용해야 한다.

 

✔️ 알고리즘

단어들을 집합(set)으로 저장하여 중복을 제거할 수 있다.

중복이 제거된 단어들을 리스트로 변환하여 정렬하고, 기준은 (단어의 길이, 단어)로 설정한다.

 

sorted() 함수를 사용하여 집합을 정렬하면 자동으로 리스트로 변환된다!

 

---

📌 코드 설계하기

- 문제 탐색하기 과정을 기반으로 이 문제를 해결하기 위한 로드맵을 그리는 과정
- 어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 단어의 개수 N을 입력한다.

2. 각각의 단어를 읽어 집합에 저장하여 중복을 제거한다.

3. 집합을 리스트로 변환 후 앞서 언급한 기준대로 정렬한다.

4. 정렬된 리스트를 순회하며 단어를 출력한다.

 

---

📌 시도 회차 수정 사항 (Optional)

무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면,

내가 어떤 실수를 해서 해당 문제를 틀렸는지 모른다.

- 틀렸습니다를 받았다면 왜 틀렸는지, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

---

📌 정답 코드

import sys
input = sys.stdin.read

def main():
    data = input().splitlines()
    N = int(data[0])
    
    words = set(data[1:]) # 중복 제거
    sorted_words = sorted(words, key=lambda x: (len(x), x)) # 기준: (단어의 길이, 단어)

    for word in sorted_words:
        print(word)

if __name__ == "__main__":
    main()

 

이번주는 정렬 알고리즘과 관련된 여러 문제를 풀고 이론도 정리하는 글을 작성해야겠다!!

 

 

코테 챌린지 3기 파이팅 :)

@why_dev_says_no