태그:
1부터 N까지 수를 한 번씩 넣었다 뺄 때 주어진 수열을 만들 수 있다면 push/pop 순서를, 아니면 NO를 출력하는 문제입니다. 우선 문제에서 주어진 규칙에 따라 스택에 push/pop 행동을 기억했다가 모순이 생기지 않는다면 그 행동을 모두 출력하는 방식을 이용하겠습니다. 문제의 조건과 스택의 구조를 생각해보면 스택의 top은 스택에 들어있는 수 중 최대값이고, 현재 top인 수가 목표 수열에 등장하기 전에 다른 스택 원소가 등장한다면 모순이 될 것입니다. 이제 현재 스택의 top과 목표로 하는 수열의 원소 값의 관계에 따라 모순인지 아닌지, 모순이 아니라면 무엇을 해야 하는지 정의해야 합니다. 총 3가지가 존재합니다.
-
출력할 숫자가 스택의 top보다 큰 경우
문제의 조건 상 스택에 push하는 값은 현재 상태의 top보다 큰 값이 들어가게 되므로 출력할 숫자와 같은 값을 향해 다가갑니다.
-
목표로 하는 수열의 숫자가 스택의 top과 같은 경우
스택을 pop하여 출력합니다.
-
목표로 하는 수열의 숫자가 스택의 top보다 작은 경우
모순이 생긴 상황입니다. NO를 출력하고 프로그램을 종료하면 됩니다.
위와 같은 행동을 반복하여 모순이 없다면, 저장한 행동을 모두 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-02 20:00:18 |