[백준/c++] 1874번 - 스택 수열

문제

1874번: 스택 수열

풀이

분류 : 큐, 스택.

 

1. 먼저 입력으로 주어지는 수열을 스택에 담습니다.

2. 0부터 시작하는 pivot을 설정합니다.

3. pivot보다 n번째 수열값이 크다면, pivot++해주면서 +-가 담기는 정답스택에도 +를 담아줍니다.

4. pivot++해주다가 pivot과 n번째 수열값이 같은 경우가 온다면 정답스택에 -를 담아주고, 수열 스택도 pop해주고 pivot-- 해줍니다.

5. pivot이 수열스택 size를 넘지 않을때까지, 수열스택이 empty가 아닐때까지 반복합니다.

6. pivot < n번째 수열값이 존재한다면 스택으로 만들 수 없는 경우이므로 반복문 break후 NO리턴해줍니다.

 

코드(O(n)) *O(n)이 아니라면 알려주세요. 감사합니다(--)(__)*