[정올 1328] 빌딩

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=1328&sca=3020 

JUNGOL

#include <cstdio>
#include <iostream>
#include <stack>

int N;//빌딩수
int H[100000 + 10];//빌딩높이
int sol[100000 + 10];//각 빌딩에서 보이는 빌딩 번호

std::stack<int> idx;
std::stack<int> stk;

void InputData(void) {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &H[i]);
	}
}

void get_tower(void)
{
	for (int i = 1; i <= N; i++) {	// 범위 조심 ! 인덱스 1부터 N까지 들어온다 !!
		while (!stk.empty() && stk.top() < H[i]) {
			sol[idx.top()] = i;
			idx.pop();
			stk.pop();
		}
		stk.push(H[i]);
		idx.push(i);
	}
}


void OutputData(void) {
	for (int i = 1; i <= N; i++) {
		printf("%d\n", sol[i]);
	}
}

int main(void) {
	InputData();//입력받는 부분

	//여기서부터 작성
	get_tower();

	OutputData();//출력하는 부분
	return 0;
}

이 문제는 앞에 "불쾌한 날" 문제를 풀었다면 쉽게 해결할 수 있다. 

로직은 동일한데, 다만 stk.top()에서 볼 수 있는 가장 큰 빌딩의 인덱스를 배열에 저장해주어야 한다는 점만 다르다. 

 

// get_tower() 함수

물론 인덱스만 스택에 저장해 놓으면 입력받은 H배열로 빌딩의 높이를 알 수 있지만, 코드 짜는 나는 헷갈리기 때문에 ㅋㅋ.. 인덱스를 저장할 스택과 높이를 저장할 스택을 각각 전역으로 만들어 주었다. (이렇게 하면 해당 함수에서 sol[idx.top()] 를 갱신하지 못한 원소는 그 값이 0이므로 따로 처리해줄 필요가 없어서 좋음)

 

현재 탐색하고 있는 빌딩의 높이( H[i] )가 stk.top()보다 크면, sol배열의 idx.top 번째 원소에 해당 빌딩의 인덱스( i )를 담아준다. 이를 스택이 비거나, stk.top()의 원소가 H[i]보다 같거나 커질때까지 반복한다. 

만약 스택이 비거나 stk.top() 원소가 H[i]보다 같거나 크면, 현재 탐색하고 있는 빌딩은 스택의 원소보다 높은 빌딩이 아니다. 따라서 스택에 쌓고 루프를 돌려 높은 빌딩을 찾는다.