1874번 스택 수열(stack, 조건문)

#문제링크 : https://www.acmicpc.net/problem/1874

N값을 입력받고, 바로 다음 줄부터 N개의 수열을 입력받는다. stack에 입력받을 때는 1부터 무조건 오름차순으로 입력받는다. stack을 사용해서 해당 수열을 만들 수 있으면 push일때, "+", pop일때, "-"를 출력한다. 크기가 N인 배열을 하나 선언하고 그 배열에 수열을 담는다. 그리고 stack이 비어있으면 입력받은 배열의 요소만큼 push해주고, 마지막에 pop을 한번 한다. stack의 top이 배열 값과 같으면 pop을 하고, top이 배열 값보다 작으면 배열값과 같아질때까지 push하고 마지막에 역시 pop을 한번 한다. 그 외의 경우, stack의 top이 배열값보다 크면 "NO"를 출력한다. 첫시도는 메모리 초과가 나왔다.

※주의사항

1. 차근차근 메커니즘 파악한다. 첫 입력값 만큼 push를 하고 pop을 한번 해줘야 하는 메커니즘임을 알자.

2. 두번째로 stack초기화(clean_pop)함수를 중간에 넣어서 초기화하여 오류가 없도록 한다.

 

1. Code

<2nd try>

수정하는 와중에 반례가 나왔다. 입력이 (5 14325) 일때 위의 코드는 NO를 출력한다. 이유는 s.empty일때, 처음과 중간에 비는경우로 나뉘는데, 중간에 비는경우를 생각하면 while문 조건에 temp2가 제로가 될때까지이므로 스택이 추가로 숫자를 더 push한다. 그래서 while 조건을 바꾸어줬고, 배열도 사용하지 않고 수정해보았다.

※주의사항

1. 반례를 잘 생각해보고, 문제의 메커니즘을 똑바로 따라가기.

2. 굳이 같은 코드를 두번 안쓰고 출력을 벡터에 담아놓는 방법을 생각하고, NO와 정상출력 구분하기.

3. 메모리를 최대한 안쓰는 방법 고안하기. (임시 배열을 사용하지 않는 것.)

2. Code