911E Stack Sorting

내가 제일 약한 자료구조문제

http://codeforces.com/problemset/problem/911/E

자료구조문제는 자료구조를 응용해서 푸는 문제이긴한데, 그 동작이 영 익숙치 않다.

이번 문제는 다음과 같다. 한 개의 큐와 한 개의 스택를 이용해 하나의 배열로 정렬하여 두어야한다.

문제는 그림으로 그려보면 대충 다음과같다.

1과 2의 동작을 할 수 있는데 array에 반드시 sorting 되어야한다.

그래서 문제 이름이 stack sorting 이다. 그래서 sorting 이 될수 없으면 -1을 반환해야한다.

문제가 여기까지이면 nice이다. (그래도 까다롭고 어려울 듯)

그런데 문제는 이 요구사항에서 한 걸음 더 나가는데, 

배열 size가 n이라고 할 때 단 k만 주어진다. 

그래서 문제 input은 다음처럼 주어질 수 있다.

5 3   (n, k) 

3 2 1

이 경우 우리는 initial을 3 2 1 4 5 , 3 2 1 5 4 로 할 수 있다.

이 상황에서 두 개 모두 sorting이 가능하다.  3 2 1 5 4 를 살펴보자.

[3 2 1 5 4]   []   []

[5 4]   [3 2 1] []    //3 2 1 -> queue pop

[5 4]  [] [1 2 3]     //1 2 3 -> stack pop

[] [5 4] [1 2 3]      //5 4    -> queue pop

[] []  [1 2 3 4 5]    //4 5    -> stack pop , sorting end

이 때 input 5, 3, [3 2 1] 에 대한 정답은 3 2 1 5 4 가 되어야한다.

3 2 1 4 5 도 가능하지만, 숫자가 가장 큰 정답을 출력해야한다. 따라서 스페셜 저지 문제가 아니라 항상 정답 하나가 존재한다. 3 2 1 5 4 처럼말이다.

우선 있는 그대로 잘 구현하면된다. 하지만 난 이걸 하지 못했고,,, 에디토리얼에서 정답을 구할 수 있엇다. 굉장히 간단한 구현이였던것 같지만, 동작원리가 몸에 와닿지 않고 예외처리가 조금 신경쓰인다. .. 

동작은 입력하자마자 스택에 넣고, 뽑아야 할것을 cur로 마크한뒤 뽑아내면된다.

그리고 예외 처리는 약간 어려운데, 좀더 성장하면 깔끔하게 풀 수 있었음좋겠다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/datastructure/911E.cc