백준 1874번 스택 수열

 

문제에 대한 출력을 이해하는데 시간이 오래 걸렸던 문제이다.

입력에 대해서 맨 첫줄에 크기를 입력 받고 리스트에 n만큼의 수를 입력 받은 후에 Stack의 push, pop을 이용하여 리스트와 동일하게 만들 수 있는가 없는가 물어보는 문제이다.

 

우선 1부터 n까지 차례대로 입력 받는 Stack1이 존재한다. (입력 1의 일부만 설명)

				8(+)	7(-)
4(+)		6(+)		7(+)	8(-)
3(+)		5(+)	6(-)	5	6
2(+)	3(-)	2	3	2	3
1(+)	4(-)	1	4	1	4

   Stack1        Stack2     Stack1       Stack2        Stack1      Stack2

 

Stack1 에서 Pop을해서 다른 Stack2에 담아두었다고 생각하면 된다.

 

최종적으로 Stack2에 있는 값과 n만큼의 수를 입력 받은 리스트가 동일하게 만들 수 있으면 사용된 push(+), pop(-) 순서대로 출력하고, 동일하게 만들 수 없으면 NO를 출력하는 문제이다.

 

Stack은 1부터 오름차순으로 입력받는 리스트로 구현했으며, push 되면 다른 배열에 +를 push 해주고 입력받는 숫자를 1개씩 높여준다.

 

1부터 오름차순으로 Stack에 쌓이기 떄문에 입력받는 리스트와 동일하게 만드려면 맨 처음 입력받는 숫자가 Stack의 최상단에 있어야 Pop을 했을 때 입력받는 리스트의 0번 인덱스의 숫자가 동일해진다.

 

NO가 나오는 조건은 (입력 2번을 예를 들어 설명)

 

[1,2,5,3,4]를 입력 받으면 Stack에는 3, 4가 있는 상황이고 다른 리스트에는 1,2,5 가 있는 상황인데 Pop을 해도 [1,2,5,4,3]

[1,2,5,3,4] 와 동일해 질 수 없기 때문에 NO를 출력해야 한다.

 

위 코드에서 설명하자면 5가 들어왔을 때 number 가 6이며 index는 3 Stack의 Top은 4이다.

즉, index와 Stack의 Top이 같지 않을 때, 입력받는 리스트를 오름차순 Stack을 Pop을 이용해 만들 수 없는 것이다.

 

문제가 이해가 안되서 빈 노트에 볼펜으로 그림 그려가면서 이해했던 문제이다.