BOJ) 단어 정렬

단어 정렬

1181번: 단어 정렬

넋두리

 

문제를 보고 풀지 말지 고민을 많이했다.

문제를 보자마자 우선순위 큐면 금방 풀리는 문제라고 떠올랐기 때문이다.

복잡한 과정 없이 자료구조 하나만 써서 풀리는 문제는 허무하다고 느끼지만, 요즘 슬럼프라서 틀리는 문제가 많아 그냥 풀었다.

 

사실 우선순위 큐 말고 ArrayList나 배열을 이용해서 풀어도 된다.

sort 메소드를 사용할 때, Comparator만 아래와 같이 작성해주면 되기 때문에..

하지만 제일 처음 떠올린게 우선순위 큐라 그냥 우선순위 큐로 풀었다.

 

compareTo 메소드에서 단어의 길이에 따라 오름차순으로 정렬하는 부분과 길이가 같은 경우에 사전 순서에 따라 정렬하는 부분만 신경써주면 될 것 같다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.PriorityQueue;

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

        while(n-- >0) {
            pq.offer(new MyWord(br.readLine()));
        }
        br.close();

        solution(pq);
    }

    private static void solution(PriorityQueue<MyWord> pq) {
        HashSet<String> set = new HashSet<>();

        while(!pq.isEmpty()) {
            String str = pq.poll().str;
            if(!set.contains(str)) {
                System.out.println(str);
            }
            set.add(str);
        }
    }
}

class MyWord implements Comparable<MyWord> {
    String str;

    public MyWord(String str) {
        this.str = str;
    }

    @Override
    public int compareTo(MyWord m) {
        if(this.str.length() > m.str.length()) {
            return 1;
        } else if(this.str.length() == m.str.length()) {
            for(int i=0; i<this.str.length(); i++) {
                if(this.str.charAt(i) > m.str.charAt(i)) {
                    return 1;
                } else if(this.str.charAt(i) < m.str.charAt(i)){
                    return -1;
                }
            }
        }
        return -1;
    }
}