[백준 1181] 단어정렬 - 자바

백준 1181 단어정렬

문제

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

길이가 짧은 것부터
길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

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

시간 제한 및 메모리 제한

2초, 256MB

문제 해결 키

Arrays.sort(arr, new Comparator<T>(){
    @Override
    public int compare(String o1, String o2){
        return 0;
    }
)

코드

package main;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main1181 {

    public static void main(String args[]) throws Exception {

        // 1. 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        /**
         * 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
         * 
         * 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 첫째 줄에 단어의 개수 N이 주어진다.(1
         * ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는
         * 50을 넘지 않는다.
         */

        int N = Integer.parseInt(st.nextToken());

        String[] words = new String[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String word = st.nextToken();
            if (word.length() > 50) {
                throw new Exception("50 자리넘어갑니다.");
            }
            words[i] = word;

        }
        // 정렬
        Arrays.sort(words, new Comparator<String>() {

            @Override
            public int compare(String word1, String word2) {
                // 숫자가 같다면 사전 순
                // 같지 않다면 길이 순으로 리턴
                return word1.length() == word2.length() ? word1.compareTo(word2) : word1.length() - word2.length();

            }
        });
        // 첫번째 요소 출력
        System.out.println(words[0]);
        // 두번째 요소 부터 앞 요소와 중복체크하며 출력
        for (int i = 1; i < words.length; i++) {
            if (!words[i].equals(words[i - 1])) {
                System.out.println(words[i]);
            }

        }

    }

}

Scanner 대신 BufferedReader를 사용

BufferedReader를 사용하는 것이 Scanner 를 사용한 입출력보다 시간이 빠르게 나온다.

Arrays.Sort() 사용

• 자바에서 제공하는 배열 정렬 라이브러리

  // 정렬
  Arrays.sort(words, new Comparator<String>() {
    @Override
    public int compare(String word1, String word2) {
        // 숫자가 같다면 사전 순
        // 같지 않다면 길이 순으로 리턴
        return word1.length() == word2.length() ? word1.compareTo(word2) : word1.length() - word2.length();
        }
  });

기본적으로 sort() 함수는 문자열을 사전단위로 정렬해준다.
하지만 이 문제에서는 문자열의 길이까지 고려를 해야하기 때문에, 위와 같이 Commparator를 compare 오버라이딩하여 정렬 조건을 구현할 수 있다.
compare 함수에서 리턴 값은 음수, 양수가 있다.
word1과 word2의 길이를 비교해서 반환을 하는데, word1이 길다면 양수, 짧다면 음수를 리턴하게 될 것이다.

위 코드의 핵심 로직은 다음과 같다.
문자열의 길이가 같다면 compareTo() 메서드로 정렬한다.compareTo() 메서드는 문자열을 사전 순으로 정렬해준다.
문자열의 길이가 다르다면 양수, 음수 값을 리턴하고, 사전 순으로 처리한다.

중복제거하여 출력

// 첫번째 요소 출력
    System.out.println(words[0]);
    // 두번째 요소 부터 앞 요소와 중복체크하며 출력
    for (int i = 1; i < words.length; i++) {
        if (!words[i].equals(words[i - 1])) {
            System.out.println(words[i]);
        }
    }

직전 원소와 비교하여 같지 않다면 출력하는 로직이다.
첫 번째 원소는 직전원소가 없기 때문에 무조건 출력한다.
2번째 원소부터 마지막원소까지 직전원소를 비교하여 같지않다면 출력하고, 같다면 중복으로 간주하고 출력하지 않는다.