티스토리 뷰
https://www.acmicpc.net/problem/17299
17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
스택인걸 알면 쉬운데 알기까지가 어려운 문제.
스택에 {숫자, F(숫자)} 를 저장한다.
뒤에서부터 앞으로 탐색하면서 스택의 top의 F(A)가 현재 F(Ai) 작거나 같을때까지 모두 pop 시킨다.
그럼 결론적으로 스택의 top에 현재 F(Ai) 보다 F(A)가 크고, 스택 자료구조 특성상 나보다 오른쪽에 있으면서 최초로 등장한것이 남게된다.
'PS' 카테고리의 다른 글
| 백준 1202. 보석 도둑 (0) | 2023.01.21 |
|---|---|
| 백준 1926. 그림 (0) | 2023.01.21 |
| 백준 1713. 후보 추천하기 (0) | 2023.01.20 |
| 백준 11780. 플로이드 2 (0) | 2023.01.20 |
| 백준 16437. 양 구출 작전 (0) | 2023.01.20 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- binary search
- Unity
- Implementation
- C++
- 조합
- db
- MVC
- Python
- 이분탐색
- recursion
- Spring
- greedy
- priority queue
- two pointer
- Tree
- 재귀
- 자료구조
- back tracking
- CSS
- Kruskal
- graph
- Brute Force
- floyd warshall
- DP
- C
- permutation
- Dijkstra
- dfs
- Stack
- BFS
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 |
글 보관함