[BOJ 1874] 스택 수열 (C++)

 

Problem

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

1874번: 스택 수열

 

Comment

문제에서 '1부터 N까지의 수를 오름차순으로 차례대로 스택에 push한다'고 명시되어 있습니다. 맨 처음에 정수 N을 받고 반복문을 통해 1부터 차례대로 넣어줍니다. 넣어주는 과정 속에서 둘째 줄부터 N개의 정수를 받을텐데, 매번 넣을 때마다 비교를 해주어야 합니다.

 

만약 스택에 A라는 수가 있고 B라는 숫자가 나오길 바란다면 (A < B) A가 B가 될 때까지 스택에 push 하고 (이 때, '+'를 출력합니다.) B를 pop (이 때, '-'를 출력합니다.) 합니다.

그렇지 않다면, "NO"를 출력합니다.

 

예제 1을 천천히 따라가면서 어떻게 동작하는지 알아보겠습니다.

 

처음에 정수 하나를 받습니다. 1부터 8까지 스택에 넣는다는 것을 알 수 있습니다.

 

<4>

4라는 숫자를 받았습니다. idx라는 변수를 선언해주고 1로 초기화해줍니다. idx는 현재 스택 제일 위에 있는 숫자라고 생각하면 됩니다. 그럼 현재 idx는 1입니다. 받은 값이 idx보다 크므로 ( while(temp >= idx) ) idx가 4가 될 때까지 push 해줍니다.

 

다 push 했다면 4를 pop 합니다.

현재 상황
- i (반복문; iterator): 1
- idx = 4
- 출력: + + + + -

 

<3>

3이라는 숫자를 받았습니다. 3은 현재 idx보다 하나 작습니다. 받은 값이 idx보다 크지 않습니다. 그렇다면 while문이 돌 필요가 없겠죠. 현재 스택 제일 위에 놓여있는 값이 3입니다. 받은 값이 3으로 같으므로 ( if(s.top() == temp ) pop 해줍니다.

현재 상황
- i (반복문; iterator): 2
- idx = 4
- 출력: + + + + -

 

<6>

6이라는 숫자를 받았습니다. 6은 현재 idx보다 큽니다. 받은 값이 idx보다 크므로 idx가 6이 될 때까지 push 해줍니다.

 

다 push 했다면 6을 pop 합니다.

현재 상황
- i (반복문; iterator): 3
- idx = 6
- 출력: + + + + - + + -

 

<8>

이제 점점 감이 잡힙니다. 8이라는 숫자를 받았습니다. 현재 idx보다 크므로 8이 될 때까지 push 해줍니다.

 

다 push 했다면 8을 pop 합니다.

현재 상황
- i (반복문; iterator): 4
- idx = 8
- 출력: + + + + - + + - + + -

 

 

<7>

7이라는 숫자를 받았습니다. 현재 스택 제일 위에 놓여있는 값이 7입니다. 받은 값이 7으로 같으므로 pop 해줍니다.

현재 상황
- i (반복문; iterator): 5
- idx = 8
- 출력: + + + + - + + - + + - -

 

<5>

5라는 숫자를 받았습니다. 현재 스택 제일 위에 놓여있는 값이 5입니다. 받은 값이 5로 같으므로 pop 해줍니다.

현재 상황
- i (반복문; iterator): 56
- idx = 8
- 출력: + + + + - + + - + + - - -

 

<2>

2라는 숫자를 받았습니다. 현재 스택 제일 위에 놓여있는 값이 2입니다. 받은 값이 2로 같으므로 pop 해줍니다.

현재 상황
- i (반복문; iterator): 7
- idx = 8
- 출력: + + + + - + + - + + - - - -

 

<1>

1이라는 숫자를 받았습니다. 현재 스택 제일 위에 놓여있는 값이 1입니다. 받은 값이 1로 같으므로 pop 해줍니다.

현재 상황
- i (반복문; iterator): 8
- idx = 8
- 출력: + + + + - + + - + + - - - - -

Code

 

Result