[PS] 99클럽 코테 스터디 3일차 TIL (문자열 내 마음대로 정렬하기)

문제

문제 링크

풀이

첫번째 풀이 (O(n^2))

class Solution {
  public String[] solution(String[] strings, int n) {
    for (int i = 0; i < strings.length; i++) {
      for (int j = i + 1; j < strings.length; j++) {
        char c = strings[i].charAt(n);
        char c1 = strings[j].charAt(n);
        if (c > c1) {
          String tmp = strings[i];
          strings[i] = strings[j];
          strings[j] = tmp;
        } else if (c == c1) {
          if (strings[i].compareTo(strings[j]) > 0) {
            String tmp = strings[i];
            strings[i] = strings[j];
            strings[j] = tmp;
          }
        }
      }
    }

    return strings;
  }
}

이중 for 문을 사용해 문자열을 비교하면서 버블정렬한다. 첫번째 조건문에서 인덱스에 해당하는 알파벳의 아스키 코드값을 비교한다. 만약 앞의 코드값이 더 큰 값을 가진다면 버블정렬을 통해 자리를 바꿔준다. 같은 코드값을 같는 알파벳의 경우엔 알파벳을 사전순으로 정렬한다. 이때 compareTo() 메소드를 이용하면 문자열을 쉽게 비교할 수 있다. (기준값과 비교대상이 같으면 0, 기준값이 더 큰 경우 양수, 비교대상이 더 큰경우 음수)

strings[i].compareTo(strings[j]) > 0 은 기준값이 비교대상보다 더 큰 경우를 의미한다. 따라서 이 경우엔 오름차순(사전순)이 되도록 자리를 바꿔 줘야한다.

해당 방식은 모든 요소를 비교하는 버블 정렬을 이용하기 때문에 효율이 좋지않다. 또한 for 문과 if 문이 많아 가독성이 좋지 않다.

두번째 풀이 (O(n log n))

class Solution {
  public String[] solution(String[] strings, int n) {
    Arrays.sort(strings, (o1, o2) -> {
      if (o1.charAt(n) == o2.charAt(n)) {
        return o1.compareTo(o2);
      } else {
        return o1.charAt(n) - o2.charAt(n);
      }
    });

    return strings;
  }
}

자바에서 배열의 정렬은 Arrays.sort() 를 이용해서 쉽게 풀 수 있다. 메소드의 첫번째 파라미터로 정렬하고자 하는 배열을 주고, 두번째 파라미터에서 정렬 방식을 설정한다.

두번째 파라미터는 Comparator 인터페이스의 compare() 메소드 구현체를 전달해 주면된다.

compare() 메소드는 두 인자를 파라미터로 전달받아 서로 비교한다.

int compare(T o1, T o2);

Arrays.sort() 는 내부적으로 Tim sort 를 사용한다. Tim sort 는 병합정렬을 기반으로 진행하되, 일정 크기 이하의 부분 리스트에 대해서는 삽입정렬을 수행하는 방식이다. 병합 정렬의 빠른 시간 복잡도와 삽입 정렬의 메모리 접근 효율성을 고려한 방식이다. (삽입정렬의 경우 인접한 메모리와의 비교를 반복하는 방식으로 진행되기 때문에 참조 지역성을 잘 만족한다.)

두번째 인자로 전달된 Comparator 구현체는 삽입정렬 내부에서 두 값의 비교에 사용된다. 즉, compare() 메소드를 통해 두 값을 비교할 때, 위에서 전달한 o1.compareTo(o2) 로 비교할 것인지, o1.charAt(n) - o2.charAt(n) 방식으로 비교할 것인지가 정해진다고 보면된다.

// TimSort.sort() 내부
...
if(nRemaining<MIN_MERGE) {
  int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
  binarySort(a, lo, hi, lo +initRunLen, c);
  return;
}

TimSort 의 countRunAndMakeAscending 메소드

TimSort.sort() 의 내부에 위와 같은 코드가 있는데, countRunAndMakeAscending 메소드는 이름 그대로 ‘sort 작업해야 할 길이를 반환하는 오름차순 제어기’ 라고 보면 된다. Arrays.sort() 내부에서 해당 메소드가 항상 호출되고 있기 때문에 기본값이 오름차순으로 유지된다는 것을 알 수 있다.

lo 는 0 즉, 첫번째 인덱스를 의미하고 hi 는 전달된 배열의 전체 길이를 의미한다. 그러면 runHi 변수 초기값은 1이된다.

if (c.compare(a[runHi++], a[lo]) < 0) 

따라서 이 부분에서 최초 a[1], a[0] 을 비교하게 된다. 즉, a[1] 과 a[0] 이 o1.compareTo(o2) 또는 o1.charAt(n) - o2.charAt(n) 표현식에 의해 평가된다. 그리고 그 연산의 결과가 음수인지를 확인하고 있다.

만약 a[1], a[0] 을 각각 ‘a’ 과 ‘b’ 라고 하면, a[1] - a[0] 는 음수가 나온다. (a = 97, b = 98) (왜 둘을 서로 빼는지는 String 의 compare 재정의 최종 결과를 보면 알 수 있다.)

따라서 해당 경우는 내림차순에 해당된다. runHi 를 1씩 증가해 가면서, 오름차순 영역이 나올때 까지 확인한다. 그러면 최종 뒤집어야 하는 갯수(runHi)가 정해지고 reverseRange 메소드를 통해 내림차순에 해당되는 부분 배열을 오름차순으로 뒤집는다.

반대로 오름차순의 경우에도 마찬가지의 방식으로 runHi 를 카운팅하고 이 갯수를 반환한다. 이 과정은 삽입 정렬 전에 배열을 오름차순으로 세팅하는 전처리 하는 과정이라고 보면 될 것 같다. 그 이후 실제로 정렬하는 작업은 binarySort() 에서 진행된다.

Tim sort 내부 insertion sort 중

정리

Arrays.sort() 에서 Comparator 로 정렬하고자 할때

o1.compareTo(o2), o1.charAt(n) - o2.charAt(n) : 오름차순 정렬
o2.compareTo(o1), o2.charAt(n) - o1.charAt(n) : 내림차순 정렬

로 기억하면 된다.