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
[문제]
[코드]
[풀이]
이 문제를 처음 풀 때는 스택을 사용한다는 것을 생각하지 못해 여러개의 if, elif 문으로 케이스를 분류해서 풀었었다. 블로그에 올라와 있는 다른 분들의 풀이를 보고 그제서야 스택으로 푸는 문제라는 것을 생각해 풀었다.
스택에 push하는 순서는 무조건 오름차순으로 하며, pop을 통해 수열을 만들어야 한다는 것이 문제의 핵심이다. 스택은 입력과 출력이 한 군데에서만 일어나기 때문에 마지막 자료만 꺼낼 수 있다는 특징이 있다. 따라서 스택의 마지막이 입력 받은 숫자와 다르다면 만들 수 없는 수열이 된다는 점을 이용하여 풀면 된다.
'Koala - 9기 > 기초 알고리즘 스터디' 카테고리의 다른 글
| [백준/python] 2745번 진법 변환 (0) | 2023.01.29 |
|---|---|
| [백준/python] 11652 카드 (0) | 2023.01.29 |
| [백준 / C++] 1316번: 그룹 단어 체커 (0) | 2023.01.28 |
| [백준 / C++] 9226번: 도깨비말 (0) | 2023.01.28 |
| [백준/C++] 13235번 팰린드롬 (0) | 2023.01.27 |
