[Stack] 백준 2493번: 탑

 이번 문제는 정말 너무너무 고생해서 푼 문제이다. 시간복잡도 때문에!!! （｀ー´）

스택으로 푸는 문제 2493번 탑에 대해서 알아보자.

2493번 탑 문제

 

 이 말들을 간단히 추려보면, 각자 다른 높이의 탑이 있는데 왼쪽으로 레이저를 쏘면 누가 맞겠는가! 그 인덱스를 출력하라는 문제이다. 조금만 자세히 읽어보면 간단히 이해할 수 있다. 여기서 나는 이 문제를 스택으로 풀기 마음 먹었으니 스택으로 푸는데... 

ಠ_ಠ

 정말 많이 고민하고 많이 시도해봤다는걸 느낄 수 있겠는가... 흑... 아무튼 빨리 본론으로 넘어가자.

 

문제 풀기 전에 주의 할 점 

일단,  문제를 풀기전에 주의할 점이 있다. 

1. 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
 
 입력값이 500,000이하이고 탑들의 높이는 100,000,000이하의 정수이다. 이 말은 우리가 cin, cout을 쓰면 시간초과가 나 가능성이 거의 99.9%라는 말이다. 꼭 printf, scanf를 쓸 것!! (입력값에 따라 입력 출력 조심하라는 이야기는 전 포스터에도 써놨다.)

2. 시간복잡도는 O(N^2)이 되면 안된다.

  이 문제에서 가장 큰 문제는 시간 복잡도이다. 시간 제한이 1.5초라고 되어있다. 그런데 시간보잡도가 제곱수가 된다? 그럼 무조건 시간초과가 날 것이라는 것이다. 많은 사람들이 여기서 시간초과 문제가 발생할 것이라 생각된다. 본인 또한 여기서 아주 오랜 시간을 들였다. 

 사실 이 두가지만 잘 숙지하면 이 문제는 잘 풀 수 있다. 이제부터 알고리즘을 살펴볼 것인데, stack에 넣은 pair에 대해 알아보자.

 

Pair란?

 이 문제에서 본인이 처음으로 안 pair클래스에 대해 알아보자. 

Pair 클래스는 말그대로 두 변수를 하나로 묶어주는 것을 뜻한다. 

헤더: <utility> 

선언 방법: pair<[type], [type]> p

함수: 
p.first  -  p의 첫번째 인자
p.second - p의 두번째 인자 
make_pair(x,y) - (x,y) pair를 만들어 줌

 

알고리즘

다음과 같은 step으로만 풀면 이 문제는 간단하게 풀린다. 

1. 하나씩 입력 받을 때 마다 (index, vlaue) pair를 만든다.
2. 스택이 비어있으면,  0을 출력하고 pair를 push해준다.
3. 스택이 비어있지 않으면, top과 입력값을 비교해주고 top이 작으면 pop, top이 크면 index를 출력해주고 반복문을 빠져 나온다.

 이 룰만 지켜준다면 이 문제는 풀 수 있다. 다음 표는 예제 입력값에 대한 스택의 변화를 보여준다. 

index	value	stack	output
1	6	(1,6)	0
2	9	(1,6)
		(2,9)	0
3	5	(2,9), (3,5)	2
4	7	(2,9), (3,5)
		(2,9)
		(2,9), (4,7)	2
5	4	(2,9), (4,7), (5,4)	4

 

이렇게 총 output은 0 0 2 2 4 이다. 

 

이번 문제를 풀면서 또 하나 배워갑니다.. 총총.. （´＿｀）나의 무지함을....

(코드는 꼭 한번씩 풀어보고 참고하세요. c++)

코드

#include <iostream>
#include <stack>
#include <utility>

using namespace std;


int main(){

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

	int count = 0;
	stack<pair<int, int>> s;
	pair<int, int> p;
	int input;

	while(count < num){

		scanf("%d", &input);
		p = make_pair(count+1, input);

		while(!s.empty()){
			if(s.top().second > input){
				printf("%d ", s.top().first);
				break;
			}
			s.pop();
		}

		if(s.empty()) printf("0 ");
		
		s.push(p);
		count++;
	}

	return 0;
}