[ 백준 - 2493 ] 탑

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

2493번: 탑

3번째 풀면서 익숙해져버린 문제

스택을 이용하는 문제인데 다른 알고리즘 보다도 스택을 사용하는 어려운 문제가 진짜 힘든 것 같다.

---

[ 📌 풀이 ]

일반적인 완전 탐색의 방법으로는 시간 초과가 나는 문제다.

탑의 개수가 500,000 개까지 들어오는데 매번 탑이 스택에 들어올 때 마다 확인 하는건 좋지 않다.

 

주어진 규칙을 활용하자.

   ◀︎⎯⎯⎯⎯⎯⎯🀆 
              🀆 
              🀆◀︎⎯⎯⎯︎⎯⎯⎯⎯⎯⎯⎯🀆 
   ◀⎯🀆       🀆                 🀆
     🀆        🀆                 🀆
     🀆        🀆◀︎⎯⎯⎯⎯🀆        🀆    
     🀆        🀆        🀆        🀆◀︎⎯⎯⎯⎯🀆
     🀆        🀆        🀆        🀆        🀆
     🀆        🀆        🀆        🀆        🀆
     🀆        🀆        🀆        🀆        🀆
     6        9        5         7        4

 

2 번째 탑(9)를 보면 알 수 있듯이 제일 큰 앞에 탑은 필요가 없다.

그래서 더 큰 탑이 들어온다면 스택에서 해당 탑보다 높이가 작은 탑은 다 빼내주면 탐색 시간이 크게 줄게된다.

 

• 높이가 높은 탑이 들어온 경우 스택에서 해당 탑 보다 낮은 탑은 제거한다.
• 제거가 끝난 상태에서 확인 할 수 있는건 두 가지 이다.
  • 현재 입력된 탑 보다 앞에 있는 탑은 입력될 탑 보다 높다. -> 수신할 탑 인덱스
  • 스택이 비어있다. -> 현재 탑의 신호를 수신할 탑이 없으니 0 출력
• 스택에 탑을 넣어준다.

---

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.12.31(Sun)
# Problem   : 탑
# Spend Time: 15m 21s
# Runtime   : 732 ms
# Memory    : 105504 KB
# Algoritm  : Stack
"""

import sys
inp = sys.stdin.readline

N = int(inp())
height = list(map(int, inp().split()))
top = []

for i in range(N):
  while top and top[-1][1] < height[i]:
    top.pop()

  if not top:
    print(0, end=" ")
  else:
    print(top[-1][0] + 1, end=" ")

  top.append((i, height[i]))

[ 📌 코드 - Java  ]

/**
* Author    : Lee In Bok 
* Date      : 2023.12.31(Sun)
* Problem   : 탑
* Spend Time: 15m 21s
* Runtime   : 732 ms
* Memory    : 105504 KB
* Algoritm  : Stack
 */

package BaekJoon.Stack.Q2493;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Q2493 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = Integer.parseInt(br.readLine());
    int[] tops = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    Stack<Top2> stack = new Stack<>();

    for(int i = 0; i < N; i++){
      Top2 t = new Top2(i, tops[i]);

      while(!stack.empty() && stack.peek().height <= t.height){
        stack.pop();
      }

      sb.append(stack.isEmpty() ? 0 : stack.peek().idx + 1).append(' ');
      stack.add(t);
    }

    System.out.println(sb);
  }
}

class Top2{
  int idx;
  int height;

  Top2(int idx, int height){
    this.idx = idx;
    this.height = height;
  }
}

---

[ 📌 결과 - Python & Java  ]

[ Result - Python & Java ]