[백준 문제 풀이] 1181번 단어 정렬

Junu Kim·2025년 12월 29일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

73/89

[1181] 단어 정렬

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

문제 유형: 정렬 (Sorting), 문자열 (String), 중복 제거 (Deduplication)
요구사항: 단어를 길이 오름차순, 길이가 같으면 사전순 오름차순으로 정렬하되 중복 단어는 한 번만 출력해야 한다.

사용 개념

자료구조
- ArrayList<String>: 단어 저장 및 정렬
- HashSet<String>: 중복 제거(개선 풀이)
알고리즘/기법
- 커스텀 정렬 기준 (Comparator)
- 중복 제거 후 정렬
핵심 키워드
- 사전순 정렬 (lexicographical order)
- 다중 키 정렬 (multi-key sort)
- 해시 기반 중복 제거 (hash-based dedup)

풀이 아이디어 및 코드

방법 1 : 처음 풀이

문제 분해

입력을 받으면서 ArrayList에 저장하되, contains로 중복이면 건너뛴다.

Comparator로 (길이 → 사전순) 기준으로 정렬한다.
핵심 로직 흐름
for each word:
    if words.contains(word) continue
    words.add(word)

words.sort(길이 오름차순, 같으면 사전순)
출력
예외 처리

중복 단어는 contains로 제거

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<String> words = new ArrayList<>();

        for(int i = 0; i < n; i++){
            String word = br.readLine();
            if(words.contains(word)){
                continue;
            }
            words.add(word);
        }

        words.sort(new StringComparator());

        StringBuilder sb = new StringBuilder();
        for(String word : words){
            sb.append(word).append("\n");
        }
        System.out.println(sb);
    }

    public static class StringComparator implements Comparator<String>{
        @Override
        public int compare(String o1, String o2) {
            if(o1.length() != o2.length()){
                return o1.length() - o2.length();
            }
            if(!o1.equals(o2)){
                return o1.compareTo(o2);
            }
            return 0;
        }
    }
}

방법 2 : HashSet으로 중복 제거 후 정렬

개선 포인트 (시간/공간)

방법 1의 병목은 words.contains(word)가 O(N) 이라서, 전체가 최악 O(N²) 로 커질 수 있다는 점이다.

중복 제거는 HashSet이 평균 O(1) 이므로 입력 단계가 훨씬 빨라진다.
핵심 로직 흐름
set에 단어 N개 추가(중복 자동 제거)
set -> list로 변환
list.sort(길이 오름차순, 같으면 사전순)
출력
예외 처리

HashSet이 중복을 자동으로 제거하므로 별도 처리 불필요

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(br.readLine()); // 중복 자동 제거
        }

        ArrayList<String> words = new ArrayList<>(set);

        words.sort((a, b) -> {
            if (a.length() != b.length()) return a.length() - b.length();
            return a.compareTo(b);
        });

        StringBuilder sb = new StringBuilder();
        for (String w : words) sb.append(w).append('\n');
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: 최악 O(N² + M log M)
- 중복 체크 contains가 누적되어 최악 O(N²) 가능
- M = 중복 제거 후 단어 수
공간 복잡도: O(M)

방법 2

시간 복잡도: 평균 O(N + M log M)
- HashSet 삽입 평균 O(1) × N
- 정렬 O(M log M)
공간 복잡도: O(M)

어려웠던 점

없음

배운 점 및 팁

중복 제거 + 정렬 문제는 보통
- 입력 단계: HashSet (또는 TreeSet/정렬 필요 시)로 중복 처리
- 출력 단계: List로 옮겨 sort
  이 조합이 가장 자주 쓰인다고 한다.
비교 함수에서 if(!o1.equals(o2)) return o1.compareTo(o2); 부분은, 길이가 같다면 그냥 return o1.compareTo(o2); 로 충분하다.