티스토리 뷰

반응형

https://www.acmicpc.net/problem/2493

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 ��

www.acmicpc.net

 

난이도 : 골드 5

 

스택과 우선순위 큐를 이용하여 풀었습니다.

스택에서 하나씩 pop 하여 우선순위 큐에 있는 값과 비교하고, pop 한 값이 더 크다면 우선순위 큐에 있는 값에 그 인덱스를 남겨줍니다.

 

문제에서 주어진 예제를 그림으로 이해하기 쉽게 표현해 봤습니다.

표 밑은 우선순위 큐(value, index)이고 좌측은 스택입니다.


메소드

void main

스택에 입력을 받고 우선순위 큐를 생성합니다.

스택에서 pop 한 값을 우선순위 큐의 peek값과 비교하여 같거나 크다면 answer에 pop한 index(st.size())를 기록한 후에 우선순위 큐에 삽입해줍니다.

 

class Top

value = 숫자, index = 그 수의 인덱스입니다.

우선순위 큐에 사용되므로 comparable을 상속받았습니다.

value의 값 순으로 정렬됩니다.

 

반응형
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/11   »
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
글 보관함