(LeetCode) 969. Pancake Sorting

문제 설명

릿코드 (leetcode, 리트코드) 의 969 번째 문제는 Pancake Sorting 이라는 이름의 문제로, 팬케이크를 뒤집듯이 배열의 특정 구간만 뒤집는 것을 계속 반복했을 때, 최종적으로 전체 배열을 정렬시키도록 만들 수 있는지 물어보는 문제이다.

위 짧은 유튜브 영상을 보면 좀 더 쉽게 이해가 될텐데, 최종적으로 가장 작은 팬케이크가 맨 위에, 가장 큰 팬케이크가 맨 아래에 가도록 정렬이 되어야 하는 것이다.

요구 입출력

이러한 상황에서, 문제가 요구하는 명확한 입/출력을 말해보겠다. 문제 링크 에 들어가보면 아래와 같이 2가지 예제가 있다.

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation:
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

즉, 팬케이크를 플립하는 기준이 되는 숫자인 k 가 될 수 있는 값들의 배열을 반환하는 함수를 구현하면 되는 것이다. 여기서는, k 가 4,2,4,3 인 형태로 팬케이크 플립을 하면 최종적으로 배열은 1,2,3,4 와 같이 전체 정렬이 완성되기 때문에 4,2,4,3 은 정답이 된다.

다만, 여러 가지 배열이 정답이 될 수 있다. 문제에서는 10 * arr.length 횟수보다 적은 플립으로 정렬했을 경우 정답으로 받아들인다고 작성되어 있다.

Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Solution

이 문제를 풀 수 있는 방법은 다양하게 있겠지만, 일단 여기서는 가장 큰 원소 하나를 맨 뒤로 보내놓고, 그 앞 원소들만 정렬하는 것을 계속 반복함으로써 모든 배열 정렬하는 방법을 고려하였다.

즉 쉽게 말하자면, 선택 정렬의 개념과 유사하게 풀었다고 보면 된다. 선택 정렬의 경우, 기본적으로 배열 중 가장 작은 원소를 ‘선택’해서 맨 앞에 있는 원소와 자리바꿈을 하고, 앞으로 이동된 원소들은 이미 정렬된 상태이므로, 그 뒤 배열들에 대해서만 계속 정렬 과정을 진행함으로써 최종적으로는 모든 원소들이 정렬되도록 만드는 방법이다.

이 문제를 풀 때에는 1) 우선 가장 큰 원소를 찾고, 2) 맨 앞에서 그 원소까지의 배열을 플립하고, 3) 다시 전체 배열을 플립함으로써 가장 큰 원소가 맨 뒤에 배치하도록 했다. 그리고 나면 맨 뒤에 있는 원소들은 이미 정렬이 된 것이므로 다음 차례에서 굳이 고려하지 않고 그 앞에 있는 배열들에 대해서만 1~3 과정을 계속 반복해주면 된다.

내가 작성한 솔루션 코드는 아래와 같다.

function findMaxIndex(arr: number[]): number {
  let idx;
  for (idx = 0; idx < arr.length; idx++) {
    if (arr[idx] === arr.length) {
      break;
    }
  }
  return idx;
}

function pancakeSort(arr: number[]): number[] {
  const flipIndices: number[] = [];

  let currentSize = arr.length;
  while (currentSize > 1) {
    const maxIndex = findMaxIndex(arr.slice(0, currentSize)) + 1;

    if (maxIndex === 1) {
      arr = arr.slice(0, currentSize).reverse();
      flipIndices.push(currentSize);
    } else if (maxIndex !== currentSize) {
      arr = [...arr.slice(0, maxIndex).reverse(), ...arr.slice(maxIndex)];
      flipIndices.push(maxIndex);

      arr = arr.slice(0, currentSize).reverse();
      flipIndices.push(currentSize);
    }
    currentSize -= 1;
  }

  return flipIndices;
}

pancakeSort() 함수가 실질적으로 제출해야 하는 함수이므로 이 함수 내용을 먼저 보자.

currentSize 라는 변수는 아직 정렬되지 않은 부분의 길이를 결정하는 변수라고 보면 된다. 즉, 제일 처음에는 전체 배열의 길이가 되지만, 그 길이를 점차 1씩 줄여나가다가 최종적으로 1이 되는 시점에 모든 원소들이 정렬이 되었으므로 반복문을 멈추면 된다.

maxIndex 라는 변수는 findMaxIndex 라는 함수의 값을 사용하였는데, 주어진 배열에 있는 원소들 중 가장 값이 큰 원소의 인덱스를 반환하는 함수를 따로 구현한 것이다.

여기서 왜 Math.max 같은 것을 쓰지 않는지 궁금할 수 있는데, 기본적으로 문제의 주어진 조건에서 각 원소는 1 ~ N 사이의 자연수들이 되기 때문이다. 따라서, 길이 N 인 배열에서 가장 큰 원소의 값은 당연히 N 이 된다. 그 값과 같은 위치가 바로 우리가 원하는 maxIndex 가 된다. (최대값 원소의 인덱스)

자, 이제 maxIndex 라는 값이 가질 수 있는 케이스가 총 3가지가 있다.

1. maxIndex 가 1 인 경우 (최대 원소가 맨 앞에 있는 경우)
2. maxIndex 가 currentSize 인 경우 (최대 원소가 맨 뒤에 있는 경우)
3. 그 외

1번의 경우 최대 원소가 맨 앞에 있으므로 그 상태에서 즉시 전체 배열을 플립하면 된다. 2번의 경우 이미 최대 원소가 맨 뒤에 있으므로 아무것도 하지 않고 다음 차례를 진행하면 된다. 그 외인 3번의 경우에는 앞서 이야기한 것처럼, 맨 앞에서 최대 원소까지의 배열만 플립하고, 그 다음에 전체 배열을 플립하면 된다.

정리

이렇게, 팬케이크 정렬 문제를 풀어보았다. 선택 정렬과 비슷하게 풀면 된다는 아이디어를 찾을 수만 있다면 그렇게 어렵지는 않은 문제이기도 하며, 난이도는 미디움 (medium) 이다. 아이디어 자체를 잘 찾아서 적당히 잘 푼 것 같으나, 이번에는 뭔가 클린하고 이쁘게 작성은 못한 거 같다.

동작은 그대로 하되 좀 더 이쁘게 작성할 방법이 있다면 댓글로 알려주시면 감사하겠습니다. (배열쪽 저장하는 부분?)