백준 1181 단어 정렬 (JAVA 자바 풀이) | 문자열 길이순, 알파벳 순 정렬, 스트링 compareTo 메서드, thenComparing 메서드

백준 1181 단어 정렬 (JAVA 자바 풀이)

 

---

 

 

 

---

 

문제의 조건대로 정렬을 구현해주면 된다. 

 

중복에 대한 제거는 문자열을 받으면서 배열에 저장할 때 해도 되고 마지막에 해도 된다. 가장 간단하게 컬렉션 Set을 이용해서 구현했다. 

 

정렬은 2가지 조건을 만족해야 한다. 

 

1. 길이순 정렬

2. 알파벳순 정렬 

 

그 전에 시간 복잡도를 생각해보자. 

 

데이터가 2만이고 시간은 2초이므로 넉넉한 편이다. Arrays.sort()는 참조형 타입에 대해 O(nlogn) 시간 복잡도를 보장하므로 (https://upcurvewave.tistory.com/379) 20,000개의 데이터에 대해 약 28만 번의 연산을 수행할 것이다. 문자열의 최대 길이는 50으로 주어졌기 때문에 여기에 50을 곱하면 약 1,400만으로 계산된다. 

 

시간 복잡도가 문제 없는 것을 알았으니 이제 구현을 하면 된다. 

 

정렬을 위해 Comparator를 구현해주면 된다. 이때 익명 클래스를 열어 직접 코드를 작성한다면 다음과 같이 될 것이다. 

 

Arrays.sort(words, new Comparator<String>() {
   @Override
   public int compare(String s1, String s2) {
      int lengthCompare = Integer.compare(s1.length(), s2.length());
      if (lengthCompare == 0) {
         return s1.compareTo(s2);
      } 
         return lengthCompare;
   }
});

 

즉 먼저 스트링의 길이를 비교한 값을 리턴하고, 만약 같다면 스트링 자체를 비교하여 리턴한다. 알파벳 순 비교를 하지 않았는데도 스트링 값 자체를 비교하는 것만으로 알파벳 비교가 된다. 이는 이미 스트링 클래스에서 다음과 같이 compareTo 함수가 구현이 되어 있기 때문이다. 

 

public int compareTo(String anotherString) {
    byte v1[] = value;
    byte v2[] = anotherString.value;
    byte coder = coder();
    if (coder == anotherString.coder()) {
        return coder == LATIN1 ? StringLatin1.compareTo(v1, v2)
                               : StringUTF16.compareTo(v1, v2);
    }
    return coder == LATIN1 ? StringLatin1.compareToUTF16(v1, v2)
                           : StringUTF16.compareToLatin1(v1, v2);
 }

이 메서드는 문자열을 다른 문자열과 비교하여 순서를 결정하는 데 사용된다. 메서드는 anotherString이라는 다른 문자열과 비교되며, 비교 결과에 따라 정수 값을 반환한다.

value와 anotherString.value는 각각 현재 String 객체와 비교 대상인 anotherString 객체의 내부 바이트 배열을 나타낸다. 여기서  LATIN1과  UTF16은 인코딩 방식의 차이를 나타낸다. coder 값이 LATIN1인 경우 StringLatin1.compareToUTF16() 메서드를 호출하여 v1과 v2를 비교한다. coder 값이 UTF16인 경우 StringUTF16.compareToLatin1() 메서드를 호출하여 v1과 v2를 비교한다.

비교 결과에 따라 음수, 양수, 또는 0을 반환한다. 음수는 현재 문자열이 비교 대상 문자열보다 작을 때, 양수는 현재 문자열이 비교 대상 문자열보다 클 때, 0은 두 문자열이 동일할 때를 나타낸다. 

 

 

이렇게 익명클래스를 직접 구현하여 정렬 기준을 설정해줄 수도 있지만 함수형 인터페이스의 특징을 활용해 보다 간결하게 작성할 수 있다. 

 

Arrays.sort(words, Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

 

먼저 Comparator.comparingInt(String::length)를 통해 String 객체의 길이를 비교하는 Comparator를 생성한다. 메서드 레퍼런스로 String의 length를 구하여 이를 기준으로 비교한다.

 

이후 thenComparing(Comparator.naturalOrder())를 통해 길이가 같은 문자열들을 알파벳 순으로 정렬하기 위한 추가적인 Comparator를 지정한다. naturalOrder()를 통해 알파벳 기준 오름차순 정렬을 수행한다.

 

thenComapring의 내부 구현을 살펴보면 다음과 같다. 

 

default Comparator<T> thenComparing(Comparator<? super T> other) {
    Objects.requireNonNull(other);
    return (Comparator<T> & Serializable) (c1, c2) -> {
        int res = compare(c1, c2);
        return (res != 0) ? res : other.compare(c1, c2);
    };
}

 

 

default 메서드로 정의된 thenComparing() 메서드는 다른 Comparator를 인자로 받는다. 

 

람다식을 이용해 두 개의 객체 c1과 c2를 비교하는 compare() 메서드를 구현하는데, 현재 Comparator 객체의 compare() 메서드를 호출하여 c1과 c2를 비교하고 해당 결과값이 0이 아니라면 결과값을 반환하고, 0이라면 other 객체의 compare() 메서드를 호출하여 c1과 c2를 비교한 결과를 반환한다. 

이렇게 함으로써 두 번째 Comparator 객체인 other를 사용하여 추가적인 정렬을 수행하도록 한다. 

이후 Comparator<T> 인터페이스를 구현한 Comparator 객체를 반환함으로써 메서드 체인 방식의 연결을 가능하게 한다. 

 

(https://upcurvewave.tistory.com/371 , https://upcurvewave.tistory.com/372)

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.Set;

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

      int wordCounts = Integer.parseInt(bufferedReader.readLine());

      String[] words = new String[wordCounts];
      int count=0;
      while(wordCounts-->0){
         words[count++] = bufferedReader.readLine();
      }

      Arrays.sort(words, Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

      // Arrays.sort(words, new Comparator<String>() {
      //     @Override
      //     public int compare(String s1, String s2) {
      //        int lengthCompare = Integer.compare(s1.length(), s2.length());
      //        if (lengthCompare == 0) {
      //           return s1.compareTo(s2);
      //        }
      //           return lengthCompare;
      //
      //     }
      // });


      Set<String> uniqueWords = new LinkedHashSet<>(Arrays.asList(words));
      uniqueWords.forEach(System.out::println);


   }
}