[Leetcode(릿코드)] 969. Pancake Sorting (Medium)

leetcode.com/problems/pancake-sorting/

Pancake Sorting - LeetCode

---

문제

정렬되지 않은 배열 arr[]이 주어진다

그리고 그 배열을 1~arr.length-1개를 골라서 뒤집을 수 있다

뒤집기를 반복하여 배열을 순차적으로 정렬하는 문제이다

 

예를들어 arr[] = {3,2,4,1}이 주어지면,

1. 먼저 앞에꺼 3개를 뒤집는다 {3,2,4} -> {4,2,3}, 그러면 {4,2,3,1}이 되고

2. 4개를 뒤집는다 {1,3,2,4}

3. 2개를 뒤집는다 {3,1,2,4}

4. 3개를 뒤집는다 {2,1,3,4}

5. 2개를 뒤집는다 {1,2,3,4}

이제 순차적으로 정렬되었다

 

결과는 뒤집은 개수를 배열로 출력하는 것이다 

즉, [3,4,2,3,2]가 답이다

 

해결

풀어볼까?