[JAVA/백준/1181] 단어정렬

1181번: 단어 정렬

 

 

정렬에 두 가지 조건이 있는 문제다.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

처음 문제를 접근할 때 사전순으로 정렬하고 길이순으로 하면 되지 않을까?라고 생각했지만 

4
aa
ab
b
a

라는 입력이 주어진다면 ab가 aa보다 먼저 출력되어 오답이 된다.

 

잘못된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());

    String[] str = new String[T];
    for (int i = 0; i < T; i++) {
      str[i] = br.readLine();
    }
    Arrays.sort(str);
    for (int i = 0; i < T; i++) {
      for (int j = i + 1; j < T; j++) {
        if (str[i].length() > str[j].length()) {
          String temp = str[j];
          str[j] = str[i];
          str[i] = temp;
        }
      }
    }
    System.out.println(str[0]);
    for (int i = 1; i < T; i++) {
      if (!str[i - 1].equals(str[i])) {
        System.out.println(str[i]);
      }
    }
  }
}

 

 

 

따라서 Comparator를 이용해야 한다.

Comparator는 오름차순으로 정렬하는 Arrays.sort에 조건을 추가해서 다양한 정렬을 할 수 있게 해준다.

 

 

Comparator는 compare 함수의 리턴값에 따라 정렬을 결정한다.

1 => 교환

0 or -1 => 그대로

 

 

우선 compare 함수를 override하여 조건을 추가해 준다.

두 문자의 길이가 같다면 사전순으로 정렬, 그렇지 않다면 길이순 정렬이다.

Arrays.sort(arr, 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();
              }
            }
          }
        }
    );

 

 

위 코드를 람다식으로 간략하게 표현할 수 있다.

Arrays.sort(arr, (o1, o2) -> {
      {
        if (o1.length() == o2.length()) {
          return o1.compareTo(o2);
        } else {
          return o1.length() - o2.length();
        }
      }
    }
);

 

 

결과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int T = Integer.parseInt(br.readLine());
    String[] arr = new String[T];

    while (T > 0) {
      T--;
      arr[T] = br.readLine();
    }
    Arrays.sort(arr, (o1, o2) -> {
      {
        if (o1.length() == o2.length()) {
          return o1.compareTo(o2);
        } else {
          return o1.length() - o2.length();
        }
      }
    }
    );

    String temp = "";
    for (
        int i = 0;
        i < arr.length; i++) {
      String str = arr[i];
      if (!temp.equals(str)) {
        sb.append(str + "\n");
      }
      temp = str;
    }
    System.out.println(sb);
  }
}