백준 1181 - 집합/문자열/정렬

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

문제 설명

오늘 문제는 알파벳 소문자로 이루어진 N개의 단어가 주어졌을 때, 아래와 같은 조건에 따라 정렬하여 출력하는 문제이다.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로
3. 중복된 단어는 하나만 남기고 제거

입력 예시

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

출력 예시

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

접근 방법 1: Set을 활용한 풀이

첫 번째 풀이 방법은 집합을 활용하여 중복을 제거하고, 정렬하는 방법이다.

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    word_set = set()
    for _ in range(n): # O(N)
        word_set.add(input().rstrip()) # 평균적으로 O(1)

    sorted_words = sorted(list(word_set), key=lambda item: (len(item), item)) # O(N) + O(NlogN) => O(NlogN)
    [print(word) for word in sorted_words] # O(N)

if __name__ == '__main__':
    solution() # O(N) + O(NlogN) + O(N) => O(NlogN) + O(2N) => O(NlogN)

Set 풀이 코드 설명

1. set()을 사용해 모든 단어를 저장하면서 중복을 제거
2. 단어 길이, 사전 순으로 정렬
   1. sorted() 함수에 key 매개변수를 사용하여 정렬 기준을 지정

Set 풀이 시간 복잡도 분석

• 단어 입력 및 set에 추가: O(N)
• 정렬: O(N log N)
• 출력: O(N)
• 전체 시간 복잡도: O(N log N)

Set 풀이 공간 복잡도 분석

• Set에 단어 저장: O(N)
• 정렬을 위해 Set을 List로 변환: 추가로 O(N)
• 따라서 총 2N의 공간이 필요하지만, 빅오 표기법에서는 O(N)

접근 방법 2: Heap을 활용한 풀이

두 번째 풀이는 힙(Heap) 자료구조를 사용하는 방식이다.

import sys, heapq

input = sys.stdin.readline

def solution():
    n = int(input())
    word_heap = []
    for _ in range(n): # O(N) * O(logN) => O(NlogN)
        word = input().rstrip() # O(1)
        heapq.heappush(word_heap, (len(word), word)) # O(logN)

    prev_word = ''
    while word_heap: # O(N) * O(logN) => O(NlogN)
        item = heapq.heappop(word_heap) # O(logN)
        if item[1] != prev_word:
            print(item[1])
            prev_word = item[1]

if __name__ == '__main__':
    solution() # O(2NlogN) => O(NlogN)

Heap 풀이 코드 설명

1. 각 단어를 (길이, 단어) 형태의 튜플로 힙에 추가.
   • 파이썬의 heapq은 우선 첫 번째 요소를 기준으로 정렬하고 길이가 같을 경우 두 번째 요소인 단어를 비교하여 사전 순으로 정렬한다.
2. 힙에서 하나씩 요소를 꺼내면서
   • 이전에 출력한 단어와 비교하여 중복을 제거한다. (이미 정렬된 상태이므로)
   • 새로운 단어만 출력한다.

Heap 풀이 시간 복잡도 분석

• 단어 입력 및 힙에 추가: O(N log N)
• 힙에서 꺼내고 출력: O(N log N)
• 전체 시간 복잡도: O(N log N)

Heap 풀이 공간 복잡도 분석

• 힙에 모든 단어를 저장: O(N)
• 별도의 컬렉션으로 변환할 필요 없이 힙에서 직접 추출하여 사용