[P&B] #77 BAEKJOON 1181

백준 1181번  단어 정렬 JAVA

문제 설명

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

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

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

입력

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

 

출력

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

 

나의 문제 풀이 코드

import java.util.*;
import java.io.*;
public class bj1181 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        Set<String> word = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            word.add(br.readLine());
        }

        // 중복 제거 후, 단어를 저장한 Set: words
        List<String> sortedWords = new ArrayList<>(word);

        // 길이가 짧은 순서로 정렬, 길이가 같으면 사전 순으로 정렬
        sortedWords.sort((s1, s2) -> {
            if (s1.length() != s2.length()) {
                return s1.length() - s2.length();
            } else {
                return s1.compareTo(s2);
            }
        });
        // 정렬된 단어 리스트: sortedWords

        // 결과 출력
        for (String str : sortedWords) {
            bw.write(str+"\n");
        }
        bw.flush();
    }
}

 

문제 풀이 코멘트

이 문제를 풀기 위해서는 TreeSet과 TreeMap에 대해 먼저 알아야 합니다.

TreeSet과 TreeMap은 Java에서 제공하는 자료 구조 중 하나로, 내부적으로 레드-블랙 트리(Red-Black Tree)라는 자료 구조를 사용하여 원소를 저장하고 관리합니다. 이러한 자료 구조를 사용하면 원소들이 정렬된 상태로 유지되며, 검색, 삽입, 삭제 연산이 빠르게 수행됩니다.

1. TreeSet:

• TreeSet은 중복을 허용하지 않고, 원소들을 자동으로 정렬하는 특성을 가지고 있습니다.
• 원소를 추가하거나 제거하는 연산의 시간 복잡도는 O(log N)입니다.
• 예시: 숫자 집합을 오름차순으로 저장하고 중복된 숫자를 허용하지 않을 때 사용될 수 있습니다. 글자의 경우 사전순으로 정렬됩니다.

2. TreeMap:

• TreeMap은 키-값 쌍을 저장하며, 키를 기준으로 정렬된 순서로 저장합니다.
• 키를 기반으로 검색, 삽입, 삭제 연산의 시간 복잡도는 O(log N)입니다.
• 예시: 주소록, 단어 빈도수 맵 등에서 사용될 수 있습니다.

TreeSet과 TreeMap은 정렬된 데이터를 관리할 때 유용하며, 검색 연산이 빠르고 중복을 허용하지 않는 TreeSet, 키-값 쌍을 관리하면서 정렬된 순서를 유지하는 TreeMap을 사용할 수 있습니다.

이 문제에서는 TreeSet을 사용하여 중복을 제거한 단어들을 사전순으로 정렬하여 저장합니다.

그 다음, 아래의 람다 표현식을 이용하여 길이가 짧은 순서대로 다시 정렬합니다.

sortedWords.sort((s1, s2) -> {
    if (s1.length() != s2.length()) {
        return s1.length() - s2.length();
    } else {
        return s1.compareTo(s2);
    }
});

• sortedWords.sort() 메서드를 호출하여 sortedWords 리스트를 정렬합니다. 이때 sort() 메서드에는 Comparator 객체를 인수로 전달합니다.
• 람다 표현식 (s1, s2) -> { ... }은 Comparator 객체를 생성하는데 사용됩니다. 이 람다 표현식은 두 개의 문자열 s1과 s2를 받아 비교합니다.
• 비교 로직은 중괄호 { ... } 내에 정의됩니다. 먼저 if (s1.length() != s2.length()) 조건을 사용하여 두 문자열의 길이를 비교합니다. 길이가 다르면 s1.length() - s2.length()을 반환하여 길이가 짧은 순서로 정렬합니다.
• 길이가 같을 경우, s1.compareTo(s2)를 사용하여 두 문자열을 사전 순으로 비교합니다. compareTo 메서드는 문자열을 사전 순으로 비교한 결과를 반환합니다.
• 이렇게 정의된 람다 표현식을 sort() 메서드에 전달하면, sortedWords 리스트가 주어진 정렬 기준에 따라 정렬됩니다. 코드가 간결하며, 읽기 쉬우며 더 직관적입니다.

아직 자료구조와 람다식을 사용하여 문제를 푸는 것이 많이 어렵다고 느껴졌습니다. 더 많은 문제를 풀어보며 익숙해져야할 것 같습니다.ㅜㅜ