[99클럽 코테스터디 TIL 17일차] 백준 1181번 단어 정렬 해설 및 풀이 (Java, Python)

백준 1181번 단어 정렬

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

---

문제

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

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

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

입력

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

 

출력

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

---

 

문제 유형

문자열

정렬

 

풀이 방법 도출

 

주어진 단어들을 길이가 짧은 순으로 정렬합니다. 만약 길이가 같다면 사전 순으로 정렬합니다.

중복 단어는 제거합니다.

 

1. BufferedReader를 사용해 빠르게 입력받고, 입력받은 단어를 Set에 저장해 중복을 제거합니다.
2. HashSet을 사용하여 중복된 단어 제거합니다.
3. Collections.sort()와 Comparator를 사용하여 단어 길이로 오름차순 정렬합니다.
4. 길이가 같으면 String.compareTo()로 사전 순으로 정렬합니다.
5. StringBuilder로 결과 문자열을 만들어 한 번에 출력합니다.

 

 

시간 복잡도

• 입력 처리: O(N)
• 중복 제거 (HashSet): O(1) 평균 → 전체 O(N)
• 리스트 정렬: O(M log M) (M = 중복 제거된 단어 수 ≤ N)
• 출력: O(M)
• 총 시간 복잡도: O(N + M log M)

---

핵심 코드 삽입 및 설명 (Java)

 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력용
        int N = Integer.parseInt(br.readLine());

        Set<String> set = new HashSet<>(); // 중복 제거를 위한 HashSet
        for (int i = 0; i < N; i++) {
            set.add(br.readLine()); // 중복 제거 자동 처리
        }

        List<String> list = new ArrayList<>(set); // 정렬을 위해 리스트로 변환

        // 커스텀 정렬: 길이 순 → 사전 순
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() == o2.length()) {
                    return o1.compareTo(o2); // 길이 같으면 사전 순
                }
                return Integer.compare(o1.length(), o2.length()); // 길이 오름차순
            }
        });

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (String str : list) {
            sb.append(str).append("\n");
        }
        System.out.print(sb);
    }
}

 

import sys

input = sys.stdin.readline

# N: 단어의 개수

N = int(input())

# words: 단어를 저장할 list

words = []

# N개의 단어를 words list에 저장

for _ in range(N):
    # sys.stdin.readline()은 '\n\'을 포함하는 입력이기 때문에 연속으로 값을 입력받는 for문에서 에러가 발생했다.
    words.append(input().strip())

# words list에서 중복 단어 제거
words = list(set(words))

# 사전 순으로 정렬
words.sort() 
# 문자열 길이 순으로 정렬
words.sort(key=len)

# words list 출력

for word in words:
    print(word)