I am visible

homepage

contact

contents

home > algorithm > baekjoon > [baekjoon] 단어 정렬 (백준 1181 java 풀이)

[baekjoon] 단어 정렬 (백준 1181 java 풀이)
algorithm 2024-11-28 - -
algorithm baekjoon step13

intro : TreeSet을 사용하면, 중복제거 및 정렬 기능을 동시에 이점을 가져올 수 있다.

백준 문제링크

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

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

출력

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

문제 풀이 (308ms)

import java.io.*;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 입력값의 개수
        int forCount = Integer.parseInt(br.readLine());
        // 중복 제거를 위한 Set 변수 선언
        // TreeSet 의 특징은 중복을 제거하고, 정렬기능을 제공한다.
        // 또한 특정 정렬 기준을 적용한 TreeSet 을 설정할 수 있다.
        Set<String> set = new TreeSet<>((o1, o2) -> {
            // 문자길이가 짧은게 앞에오도록 오름차순 정렬
            if (o1.length() != o2.length()) {
                return o1.length() - o2.length();
            } else {
                // 문자길이가 같을때, 사전순으로 정렬될 수 있도록 정렬
                return o1.compareTo(o2);
            }
        });

        // 입력값을 set 변수에 저장
        for (int i = 0; i < forCount; i++) set.add(br.readLine());
        // 정렬된 set 데이터 sb.append() 메서드를 통해 저장
        for (String str : set) sb.append(str).append("\n");

        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(sb.toString());
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }
}

문제 해석

정렬하는 문제를 좀 풀어봤다 싶지만, TreeSet을 통해 푸는 방법이 굉장히 좋은거 같다. 중복제거를 해줌과 동시에 정렬기준또한 변수 선언시에 정할 수 있다. 처음에는 위 방식으로 코드를 작성했던 것이 아닌 아래 코드처럼 List를 통한 정렬을 했었다.

328ms 소요

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 입력값의 개수
        int forCount = Integer.parseInt(br.readLine());
        // 중복 제거를 위한 Set 변수 선언
        Set<String> set = new HashSet<>();
        for (int i = 0; i < forCount; i++) {
            set.add(br.readLine());
        }

        // 정렬하기 위한 List 변수 선언 (Set 을 통해 생성)
        List<String> list = new ArrayList<>(set);
        // 정렬 진행
        list.sort((o1, o2) -> {
            // 문자열 길이기준으로 오름차순 정렬 (짧으면 앞으로 옴)
            if (o1.length() != o2.length()) {
                return o1.length() - o2.length();
            } else {
                // 길이가 같으면 사전순으로 정렬
                return o1.compareTo(o2);
            }
        });

        // 반복문을 통해 sb.append() 메서드 호출
        for (String str : list) {
            sb.append(str).append("\n");
        }

        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(sb.toString());
        bw.flush();
        // 자원 반납
        bw.close();
        br.close();
    }
}

기존에도 많이 사용하던 방법이라, 이질감 없이 코드를 작성하고 문제를 풀어냈는데, 중복을 제거하고 정렬하는 부분이 다른 자료구조를 사용하면 더 편하게 처리할 수 있을거 같다는 생각이 들어서 찬찬히 생각해보니, TreeSet 자료구조가 있었다.

왜 TreeSet을 사용하는가 ?

TreeSet은 다음과 같은 특징이 있다. 중복을 제거하며, 정렬한 데이터를 제공해준다. 추가적으로 정렬을 하는 기준을 내가 커스터마이징하여 지정할 수 있다. 비슷한 자료구조 중에 PriorityQueue에도 정렬기능을 커스터마이징 하는게 있는데 TreeSet 또한 그렇다.

TreeSet을 사용하면서 얻는 이점

TreeSet을 사용하니 기존에 코드에서 다음과 같은 이점이 생긴다. Set에서 List로 변환할 필요가 없다. List를 통해 따로 Sort() 메서드를 호출할 필요가 없다. 또한 코드가 간결해지며 직관적으로 작성된다.

마무리

문제에 따라 사용하는 자료구조에 따라, 수행시간과 코드 가독성에도 큰 영향을 미치는게 위 문제를 통해 많이 느껴진다.