문제
https://www.acmicpc.net/problem/1874
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
풀이
Stack을 사용해서 풀 수 있는 문제입니다.
1부터 n까지의 수를 Stack에 넣어주고, 뽑으면서 수열을 만들게 됩니다.
예를들어 초기 입력에서 4가 주어졌다면
1, 2, 3, 4 를 Stack에 넣고 뽑아주면 4를 뽑을 수 있습니다.
그 이후로 Stack에 넣을 수 있는 수는 5, 6, 7 ... 일 것입니다.
이것을 어떻게 구현할 수 있을까요?
저는 1부터 n까지 증가할 변수 하나를 따로 두었습니다.
그리고 입력을 받게 되는데, 이 변수가 입력보다 작다면
입력의 크기와 같아질 때까지 1씩 증가시키면서 Stack에 삽입시켜줍시다.
그 이후 Stack에 삭제 연산을 해주면 입력의 수를 뽑아낼 수 있겠죠?
1부터 n까지 증가할 변수가 입력의 크기보다 크다면
Stack의 삭제 연산으로 밖에 입력의 수를 뽑아낼 수 밖에 없습니다.
즉, Stack의 마지막 요소가 입력의 수여야지만 뽑아낼 수 있습니다.
Stack의 마지막 요소가 입력의 수가 되지 못한다면, 스택 수열을 만들 수 없게됩니다.
소스코드
후기
1부터 n까지 증가할 변수를 따로 두어서 관리를 해주어야 합니다.
스택 수열을 이루는 과정을 잘 생각해보고, 스택 수열을 이루지 못하는 경우의 조건을 생각해서 풀이할 수 있었습니다.
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 2164 카드 2 (Swift) (0) | 2023.04.03 |
|---|---|
| [BOJ] 백준 18258 큐 2 (Swift) (0) | 2023.04.03 |
| [BOJ] 백준 4949 균형잡힌 세상 (Swift) (0) | 2023.04.03 |
| [BOJ] 백준 9012 괄호 (Swift) (0) | 2023.04.03 |
| [BOJ] 백준 10773 제로 (Swift) (0) | 2023.04.03 |
