[C/C++] 코드업(codeup) 4654번 탑

▽문제 바로가기

https://codeup.kr/problem.php?id=4654

탑

---

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다.

둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다.

탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

 

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다.

만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

 

문제 풀이

 

입력이 최대 500000(5십만)까지 가능합니다. 무작정 완전 탐색을 진행한다면 십억이 넘는 매우 큰 수이므로 시간 초과가 발생합니다.

 

스택을 이용해서 탐색을 줄일 필요가 있습니다.

예를 들어 ( 6 9 5 ) 가 입력되었습니다.

 

6입력 : 아무것도 없으므로 6을 push

9입력 : 입력된 9는 top인 6보다 크므로 6을 pop 해줍니다. -> 아무것도 없으므로 9 push

이렇게 해주는 이유는 이후에 어떤 값이 입력되어도 9는 6보다 크므로 6에게 수신될 수 없습니다. 이런 과정을 통해서 비교 계산해야 하는 수가 줄어들 수 있습니다.

 

하지만, 탑의 높이를 출력하는 것이 아니라 수신한 탑들의 번호를 출력해야 하므로 비교하기 위한 탑의 높이와 탑의 번호를 모두 저장해야 합니다.

 

5입력 : 입력된 5는 top인 9보다 작으므로 5를 push

 

#include <stdio.h>
#include <vector>

using namespace std;

int main(){
	
	int n;
	scanf("%d", &n);
	
	vector <pair <int , int> > arr(n);
	int top = -1;
	for(int i=0;i<n;i++){
		scanf("%d", &arr[i].first);
		
		if(top==-1){
			top++;
			arr[top].second = i;
			arr[top].first = arr[i].first;
			printf("0 ");
			continue;
		}
		
		//자신보다 큰 탑을 만날때까지 pop 
		while(top>=0&&arr[top].first<arr[i].first){
			top--;
		}
		
		//스택이 비었다면 push하고 0출력
		if(top==-1){
			top++;
			arr[top].second = i;
			arr[top].first = arr[i].first;
			printf("0 ");
			continue;
		}
		
		//pair의 앞쪽값은 탑의 높이, 뒤족값은 몇번째 탑인지
		top++;
		arr[top].second = i;
		arr[top].first = arr[i].first;
		
		//자신보다 큰 탑이 몇번째인지 출력
		if(top>=1) printf("%d ", arr[top-1].second+1);
		else printf("0 ");	//자신보다 큰 탑이 없으면 0 
		
	}
	
	
}