끄적끄적
백준 [2493] 탑 본문
출처 : https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
왼쪽에서 오른쪽 방향으로 진행한다.
현재 탑과 stack 안에 있는 top을 비교하여 top보다 현재 탑이 크면 현재 탑에 부딪히므로 top은 필요가 없어서 pop하고 현재탑 push
top보다 현재 탑이 작으면 pop시키지 않고 현재탑 push(우선순위는 거리이므로)
이때 top에 해당하는 탑을 pop하지 않는 이유는 뒤에 현재탑보다 크면서 top보다 작은 탑이 존재할 수 있기 때문
1. c++
탑의 값과 index를 같이 저장해야하므로 pair를 사용하였다.
'코테준비 > 백준' 카테고리의 다른 글
백준 23304 [아카라카] (0) | 2022.07.18 |
---|---|
백준 17298 [오큰수] (0) | 2022.04.21 |
백준 [2504] 괄호의 값 c++, python - stack (0) | 2022.04.18 |
파이썬 11주차 - 간단한 자료구조 문제와 동적 계획법 (0) | 2021.11.15 |
파이썬 스터디 10주차 - 간단한 수학, 문자열, 정렬, 이분탐색 (0) | 2021.11.04 |