[AC] 1874 스택 수열

출처 : https://www.acmicpc.net/problem/1874

해답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1874.cpp

예전부터 풀어야지 하며 안풀었던 문제를 드디어 풀었다. 엄청 간단할줄 알았는데 생각외로 해맸다. 졸려서 그런거 같다.

이 문제는 이름만 봐도 스택을 써야할듯한 문제이다. 내용도 스택을 쓰세요~~ 라고 말하는것 같다. 하지만 경험상 스택문제의 경우 거의 대다수는 스택이 필요없고 배열로만 할 수 있으며, 훨씬 속도면에서 빠르다. 구현도 훨씬 쉽다. 그러나 큐나 리스트같은경우는 배열로는 답이 나오지 않는 경우가 대다수이다.

이 문제에 먼저 기억해야할 점은 불가능한경우 NO를 출력하라고 한 점이다. 불가능할 경우가 있다는 말이니 예외처리를 해줘야한다. 나는 역시 이부분을 놓쳤다가 나중에서야 다시봤다. 하지만 이번엔 빨리 캐치해냈다.

풀이를 살펴보면 다음과 같다.

1. 입력을 받아 스택의 최상단 값과 비교를 한다.

2. 입력값이 최상단 값보다 크다면 현재 사용된 가장 큰 수부터 입력값까지 스택에 새로이 쌓는다.

3. 그 후에 최상단 값과 입력값을 비교한다.

4. 일치하면 최상단 스택을 지워버리고, 일치하지 않는다면 불가능한 경우다.

여기서 설명을 덧붙이자면 스택에는 현재 숫자의 입력에 따라 순차적으로 쌓여있다. 그런데 입력값이 스택의 최상단 값과 일치하지 않는다는 말은 스택의 순서를 무시한 경우이거나, 이미 사용된 수이거나, 전혀 관련없는 수일가능성이 높다. 그렇기 때문에 불가능한 경우가 된다. 이해가 되지 않는다면 역시 손으로 써보면서 증명해보는게 최고다. 그리 어렵지 않은 문제였다.