[백준] - 단어 정렬(1181번) (자바/Java)

 

 

 

 

사실문제를 풀면서 아직 많이 부족하다는 점을 많이 느꼈다. 

그래서 구글링을 통해 접근 방법과 어떻게 풀었는지 확인 후 이해과정을 거쳐 자료들을 참고했다.

 - 알고리즘 [ 접근 방법] -

Arrays.sort에 Comparator을 써서 compare 메서드를 구현하는 방법으로 접근했다.

 

우선 간략하게 설명 하면 Arrays.sort()는 단순 배열을 오름차순으로 정렬해 주는 뿐만 아니라 사용자에 의해 구현할 수 있다.

 

Comparator <? super T> C 란?

 

Arrays.sort() 메서드 안에는 두 객체(원소)를 비교하여 위치를 바꿀지 말지 판단하면서 정렬을 한다.

Comparator는 객체를 비교할 수 있도록 해주는 인터페이스이다. 보통 int, char, double 등의 자바에서 제공하는 자료형들은 비교가 가능하지만, 사용자 클래스를 만들어 비교한다거나, 특정 규칙에 의해 비교를 하고 싶은 경우에는 Comparator를 구현해야 한다.

 

일단 간단히 설명만 하자면, <? super T>는 상속관계에 있는 타입만 자료형으로 받겠다는 의미이다. 즉 T 타입이 자식클래스가 되고, T의 상속관계에 있는 타입까지만 허용하겠다는 의미다. 이해하기 어렵다면 물음표는 생략하고 <T>로 생각해도 좋다.

 

더 쉽게 말하자면 T = Type을 의미하며 객체, 자료형 등의 다양한 타입 중 하나를 설정할 수 있다는 것이다.

 

우리가 해야할 것은 단어 정렬이니 정렬할 배열의 타입은 String 이 될 것이다. 즉 T는 String 이 된다는 것이다.

이렇게 Comparator 의 타입을 넣었으면, 다음으로 해야 할 것은 compare 메서드를 오버라이딩하는 것이다. 

아래 코드가 기본형이 된다.

 

  String[] store = new String[num]; // 배열에 단어가 이미 초기화 되었다고 가정

        Arrays.sort(store, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
              /*
               정렬방법 구현
              */

            }
        });

 

 

그리고 compare 메소드메서드 리턴 타입이 왜 int형이냐고 한다면, 기본적으로 compare 메서드는 3가지 리턴 값에 의해 위치를 바꿀지 결정하게 된다. 3가지 리턴 값이라 하면 다음과 같다.

- 양의 정수

- 0

- 음의 정수

 

기본적으로 양수일경우 Arrays.sort()에서 정렬 알고리즘에 의해 위치를 바꾸고, 0이나 음의 정수인 경우는 두 객체의 위치는 바뀌지 않는다.

예를 들어 {2,1,3}이라는 배열이 있고, public int compare(int a1, int a2) {return a1 - a2}가 있다고 가정해 보자.

 

그렇다면 맨 처음 a1은 2가 될 테고, a2는 1이 된다. 즉 2 - 1 = 1 이므로 양수가 반환되기 때문에 a1과 a2, 즉 2와 1의 위치가 서로 바뀌게 된다. 그러면 {1,2,3} 이 된다.

 

그다음 a1, a2는 각각 2와 3이 될 테고, 2 - 3 = -1 이므로 음수가 반환되어 두 객체 2와 3은 위치가 바뀌지 않는다.

 

이렇게 compare 메서드는 3가지 반환값에 의해 두 객체(인자)의 우선순위를 판단하고, 이를 정렬 알고리즘 안에서 위치를 바꾸거나 그대로 둔다.

 

- 풀이 - 

Scanner 사용

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        String[] store = new String[num];

        sc.nextLine(); //개행 버림

        for (int i = 0; i < num; i++) {
            store[i] = sc.nextLine();
        }

        Arrays.sort(store, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                //단어 길이가 같을 경우
                if (o1.length() == o2.length()) {
                    return o1.compareTo(o2);
                }
                //그 외의 경우
                else {
                    return o1.length() - o2.length();
                }

            }
        });

        System.out.println(store[0]);

        for (int i = 1; i < num; i++) {
            //중복되지 않은 단어만 출력
            if (!store[i].equals(store[i - 1])) {
                System.out.println(store[i]);
            }
        }

    }
}

 

배열에 모든 원소를 입력받아 저장하고 sort()를 사용하여 위에서 배웠던 Comparator을 통해 정렬을 한다.

그러면 길이 순으로 정렬이 되고 길이가 같을 경우는 사전 순으로 정렬이 된다.

 

이때 출력할 때에는 정렬된 배열에서 출력하려는 문자열이 직전 배열에 있는 문자열과 같지 않을 경우만 출력하여 문제의 조건대로 ' 중복되는 문자열은 한 번만 출력 ' 하도록 한다.

 

 

※ 참고 : https://st-lab.tistory.com/112 (개인적으로 많은 도움을 받고 있는 블로그이다.)