[알고리즘][Python][C++] 백준 2493 탑 문제 풀이

문제 출처 : www.acmicpc.net/problem/2493

2493번: 탑

---

문제 해석 : 자신의 왼쪽으로만 전파를 쏘는 타워가 있다. 이 전파를 수신하기 위해서는 이보다 큰 타워여야한다. 이때 자신의 전파를 받는 전파의 인덱스를 출력하라.

 

문제 풀이 :  일반적인 투포인터, 2중 for문으로는 500,000만개의 타워를 처리할 수 없기 때문에 Stack을 이용해야 한다.

 

풀이 시간 (기록용) : 1시간

 

---

풀이 코드 (Python)

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
top = deque(list(map(int, input().split())))
stack = []
answer = []
i = 0
while top:
    value, index = top.popleft(), i

    while stack:
        if stack[-1][0] > value:
            answer.append(stack[-1][1] + 1)
            stack.append([value, index])
            break
        else:
            stack.pop()

    if len(stack) == 0:
        answer.append(0)
        stack.append([value, index])
    i += 1

for element in answer:
    print(element, end = " ")

풀이 코드 (C++)

#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;

int main()
{

    int n;
    scanf("%d", &n);

    int top[500001];
    int answer[500001];
    deque<vector<int>> stack;

    for (int i = 0; i < n; i++)
    {
        int temp;
        scanf("%d", &temp);
        top[i] = temp;
    }

    for (int i = 0; i <n; i++){
        while (!stack.empty()){
            if (stack.back()[0] >= top[i]){
                answer[i] = stack.back()[1] + 1;
                vector<int> temp = {top[i], i};
                stack.push_back(temp);
                break;
            }
            else{
                stack.pop_back();
            }
        }

        if (stack.empty()){
            answer[i] = 0;
            vector<int> temp = {top[i], i};
            stack.push_back(temp);
        }
    }


    for (int i = 0; i < n; i++)
    {
        printf("%d ", answer[i]);
    }
    return 0;
}

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.