반응형
문제
https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
풀이
스택 자료구조를 사용해서 풀이할 수 있는 문제입니다.
스택에 수를 하나씩 넣어주고, 스택의 Top이 현재 수보다 작다면 현재 수가 오큰수가 될 것입니다.
예를들어 5, 2, 7 이란 수가 있고, 현재 스택에 5, 2 까지 들어오고 7을 살펴보고 있다면
7이 현재 스택의 Top인 2보다 크기 때문에 2의 오큰수는 7이되고 2를 pop 해줍니다.
7이 현재 스택의 Top인 5보다 크기 때문에 5의 오큰수도 7이됩니다.
이러한 과정을 구하기 위해 스택에 index를 넣어주는 방식으로 구현했습니다.
소스코드
후기
Stack에 index를 넣는다는 것이 낯설었던 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 (Swift) (0) | 2023.04.26 |
|---|---|
| [BOJ] 백준 17299 오등큰수 (Swift) (0) | 2023.04.26 |
| [BOJ] 백준 9935 문자열 폭발 (Swift) (0) | 2023.04.26 |
| [BOJ] 백준 25551 멋쟁이 포닉스 (Swift) (0) | 2023.04.20 |
| [BOJ] 백준 11286 절댓값 힙 (Swift) (1) | 2023.04.20 |
