Pramp - Pancake Sort

6번째 pramp mock interview

문제

• 주어진 배열을 오름차순 정렬하는 pancakeSort(arr) 함수를 구현 하라, 단 flip(arr, k)만 사용할 수 있다.
• flip(arr, k): arr[]에서 처음부터 k 개의 요소를 뒤집는 함수. (이것도 구현해야함)

input:  arr = [1, 5, 4, 3, 2]
output: [1, 2, 3, 4, 5] # to clarify, this is pancakeSort's output

https://www.pramp.com/challenge/3QnxW6xoPLTNl5jX5LM1

총평

첨 보는 유형의 문제라 막막했다 당황했음. 하지만 결국 생각을 전개해 나가면서 솔루션 알고리즘을 찾았다. (스스로 너무 대견 ㅜㅜ). 예전에는 문제를 보고 막혔을때 -> "아 이시험 망했다" 이렇게 생각하고 더이상 나아가지를 못했던것 같다. 그런데 여러번 mock인터뷰 경험을 해보면서, 막혀도 결국 포기하지 않고 붙잡고 있다보면 결국 어떻게든 해결하게 된다는걸 깨달았다. mock인터뷰는 이렇게 막혔을때, 잘 안될때 상황을 많이 경험해봄으로써 그 상황에 대한 대응력을 키울 수 있는 훈련인것 같다. 조금 더 개선해야할 부분은 막혔을때, 어떤게 막혔는지 왜 막혔는지 언어화 해서 상대방에게 정확하게 전달하는 훈련이 필요한것같다.

실제 코딩에 대해서는, 실수를 많이 했다. 배열 인덱싱은 항상 실수를 유발한다. 시간에 쫒기지 말고 조금 더 차분히 코드를 작성하는게 좋을것같다.

받았던 피드백은 아래와 같음.

• Things you did well:
  good understanding of the problem and managed to come with optimal solution without many hints

• Things you should work on:
  try to improve in debugging code and testing code

해결 아이디어

가장 큰값을 맨 마지막으로 순차적으로 보내는 동작을 반복.

total = arr.size()
1. find biggest one's index (from 0 ~ total) -> k
2. flip(arr, k+1)
3. flip(arr, total)
4. total--

1,2,3,4를 반복한다. total이 1이 될때 까지.

예를 들어 배열값이 이렇게 주어진다고 할때: 1 5 4 3 2

1. 가장 큰 값을 [0] ~ [total - 1] 인덱스 사이에서 찾는다. -> [1] (값은 5)

[1 5] 4 3 2 

2. [0] ~ [1] 을 뒤집는다. 그러면 가장 큰값이 맨 처음으로 이동하게 된다.

[5 1] 4 3 2

3. 그리고 [0] ~ [total - 1] 을 통째로 뒤집으면 가장 큰값이 맨 뒤로 이동한다.

2 3 4 1 / 5

그 뒤 total 값은 4가 된다. 4개의 배열에서 가장 큰 값 인덱스를 찾는다. -> [2] (값은 4)

[2 3 4] 1 / 5

뒤집는다.

4 3 2 1 / 5

그리고 total사이즈만큼 통째로 뒤집는다.

1 2 3 / 4 5

맨 뒤의 값부터 순차적으로 정렬이 된다. 이 반복을 언제 멈추나를 고민해봤는데, 그냥 고려하지 않고 끝까지 반복을 해도 상관 없다.

해결 O(n^2) / O(1)

시간 복잡도는 O(n^2), 공간 복잡도는 배열을 그대로 사용했기 때문에 O(1)이다.

#include <iostream>
#include <vector>
using namespace std;

void flip(vector<int> &arr, int asize) {
  for (int i = 0; i < asize / 2; i++) {
    int tmp = arr[i];
    arr[i] = arr[asize - i - 1];
    arr[asize - i - 1] = tmp;
  }
}

int search_maxidx(vector<int> arr, int size) {
  int max = INT_MIN;
  int max_idx = 0;
  for (int i = 0; i < size; i++) {
    if (arr[i] > max) {
      max = arr[i];
      max_idx = i;
    }
  }
  return max_idx;
}

vector<int> pancakeSort( const vector<int>& orig_arr ) 
{
  vector<int> arr = orig_arr;
  int total = arr.size();
  int max_idx = 0;
  for (int i = total; i > 0; i--) { // O(n^2) / O(1) 
    max_idx = search_maxidx(arr, i);
    flip(arr, max_idx + 1);
    flip(arr, i);
  }
  return arr;
}