[백준 2493] 탑 cpp-py

문제
일직선 위에 N개의 높이가 서로 다른 탑을 왼쪽부터 세운다.
각 탑의 꼭대기에 송신기를 설치하였고 송신기는 일직선과 평행하게 왼쪽으로 발사한다. 그리고 모든 탑의 기둥에는 수신기가 설치되어있어서 다른 탑의 신호를 받을 수 있다.
이때 각 탑들이 신호를 보낼 때 몇 번째의 탑이 수신을 하는지 구하라.

6 9 5 7이라면 7은 9가, 5도 9가 수신을 하게된다.

입력
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. (1이상 500,000이하)
두 번째 줄에 탑의 높이가 N개 주어진다.

출력
각 자리의 탑이 송신한 신호를 수신하는 탑의 위치를 출력한다.

---

접근

처음에 두 개의 FOR문으로 현재 탑을 기준으로 인덱스를 줄여가면서 왼쪽으로 탐색하도록 설계를 하였다. 하지만 시간초과가 발생하였는데 O(500,000^2)의 시간복잡도를 갖는다고 생각하였지만 정확히는 아직 모르겠다.

 

그래서 왼쪽으로 탐색을 할 때 자신보다 큰 최대높이의 탑을 찾는 것이기 때문에 스택을 이용하기로 하였다.

스택은 마지막에 넣은 것이 가장 위에 쌓이는 구조이기 때문에 가장 위에있는 것이 자신을 기준으로 왼쪽에 있는 탑들의 높이다.

 

구현

스택을 선언하는데 첫 번째 인자에는 높이, 두 번째 인자에는 위치를 담는다.

	int N;
	int height;
	stack<pair<int,int>> st;

	scanf("%d", &N);

 

N개의 탑 높이를 입력할 때마다 아래의 로직을 실행한다.

만약 스택이 비어있다면 0을 출력한다. 왼쪽에 자신보다 큰 탑이 없다는 뜻이다.

그리고 스택이 비어있지 않다면 가장 위에있는 탑과 비교를 한다. 여기서 입력된 높이 이상이라면 탑의 위치를 출력하고 종료시킨다. 종료시킨다면 계속해서 가장 높은 탑이 스택의 TOP에 위치한다.

하지만 계속해서 자신보다 큰 탑이 나오지 않는다면 POP을 진행한다.

위의 두 개의 과정을 모두 거치고 마지막에는 스택에 현재의 탑의 높이와 위치를 입력해준다.

 

위의 과정은 계속해서 입력받은 탑의 왼쪽부터 검사하게되는 구조가 된다.

	for (int i = 0; i < N; i++) {
		scanf("%d", &height);
		while (!st.empty()) {
			if (st.top().first >= height) {
				printf("%d ", st.top().second);
				break;
			}
			st.pop();
		}
		if (st.empty()) {
			printf("0 ");
		}
		st.push({ height, i + 1 });
	}

---

전체 코드

 

c++

#include <iostream>
#include<algorithm>
#include <vector>
#include<cstring>
#include<stack>
// 2/5
using namespace std;



int main()
{	

	int N;
	int height;
	stack<pair<int,int>> st;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &height);
		while (!st.empty()) {
			if (st.top().first >= height) {
				printf("%d ", st.top().second);
				break;
			}
			st.pop();
		}
		if (st.empty()) {
			printf("0 ");
		}
		st.push({ height, i + 1 });
	}
	return 0;
}

 

python

python으로 다시 풀어봤다.

이 문제에서 스택을 활용하는 이유는 왼쪽부터 순차적으로 탐색할 때 현재 탑을 기준으로 이전에 자신보다 큰 탑이 있는지 알 수 있기위해서이다. 

N = int(input())
topList = list(map(int, input().split()))

stack = []
answer = []

for k, v in enumerate(topList):
    if not stack:
        answer.append(0)
        stack.append((v, k+1))
        continue
    while stack and stack[-1][0] < v:
        stack.pop()

    if stack:
        answer.append(stack[-1][1])
    else:
        answer.append(0)
    stack.append((v, k + 1))
print(*answer)