[C++] 백준 1874번 스택 수열

자료구조를 이용해서 푸는 문제.

스택 ADT에 대한 이해가 잘 돼있다면 쉽게 머리속에 그려낼 수 있다.

 

접근 방법

우선 예시로 주어진 테스트 케이스 1번 [4, 3, 6, 8, 7, 5, 2, 1]을 이용해서 살펴보자.

입력은 오름차순으로 이루어지므로 1, 2, 3, ...의 순서로 입력된다.

입력을 받을때마다 다음의 상황을 고려한다.

• 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 같다면 스택에 push한 후 pop한다. 이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop해준다.
• 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 다르다면 스택에 push만 한다.

예시상황으로 한번 살펴보겠다.

1 : 스택에 push하면 스택이 { 1 }의 상황이고 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 4와 다르므로 넘어간다.

 

2 : 스택에 push하면 스택이 { 1, 2 }의 상황이고 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 4와 다르므로 넘어간다.

 

3 : 스택에 push하면 스택이 { 1, 2, 3 }의 상황이고 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 4와 다르므로 넘어간다.

 

4 : 스택에 push하면 스택이 { 1, 2, 3, 4 }의 상황이고 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 4와 같으므로 스택에서 pop한다.

그러면 스택이 { 1, 2, 3 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 3과 같으므로 스택에서 pop한다.

그러면 스택이 { 1, 2 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 6과 다르므로 넘어간다.

 

5 : 스택에 push하면 스택이 { 1, 2, 5 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 6과 다르므로 넘어간다.

 

6 : 스택에 push하면 스택이 { 1, 2, 5, 6 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 6과 같으므로 스택에서 pop한다. 그러면 스택이 { 1, 2, 5 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 8과 다르므로 넘어간다.

 

7 : 스택에 push하면 스택이 { 1, 2, 5, 7 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 8과 다르므로 넘어간다.

 

8 : 스택에 push하면 스택이 { 1, 2, 5, 7, 8 }의 상황이고 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 8과 같으므로 스택에서 pop한다.

그러면 스택이 { 1, 2, 5, 7 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 7과 같으므로 스택에서 pop한다.

그러면 스택이 { 1, 2, 5 }의 상황이고 수열 수열 [4, 3, 6, 8, 7, 5, 2, 1]에서 계속해서 pop해주면 수열의 순서가 맞춰진다.

 

이러한 방식으로 만들면 된다.

두번 째 케이스를 보자

[1, 2, 5, 3, 4]의 수열을 만들 때,

1 - push & pop

2 - push & pop

3 - push

4 - push

5 - push & pop 이 때 스택의 top은 4인데 수열에 넣어야 하는 수는 3이므로 이는 만들수 없는 수열이다.

 

문제 풀이

 

사용한 STL과 변수

먼저 입력받는 수 n과

push할 때 '+'와 pop할 때 '-'를 담을 큐 result_queue를 만들었다.

이는 스택에 push하는 순서와 pop하는 순서는 선입선출구조로 나타내야 하기 때문이다.

수열의 수를 입력받을 큐 q도 만들었다.

그리고 수를 스택에 넣을 스택 st를 사용했다.

 

메인함수 전문

(마지막에 return 0;는 생략하겠다.)

우선 처음에 n을 입력받고 수열의 수를 순서대로 입력받아서 큐에 집어넣는다.

그러고 나서 1 ~ n까지 스택에 오름차순으로 넣을 때, 수열에 넣어야 하는 수와 스택의 최상위 수가 같다면 스택에서 pop해준다.

만일 마지막까지 입력했는데도 수열을 나타내는 큐가 비어있지 않다면(즉, 입력되지 않은 수가 있다면)

만들 수 없는 수열이 되고

큐가 비어있다면 이는 수열의 모든 수를 입력한 것이므로 push, pop한 순서를 출력해준다.

 

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.