[백준/c++] 2493번 탑 풀이(골드5)

백준에 'BaaaaaaaaaaarkingDog'님이 알고리즘 종류별로 문제집을 만들어 놓으신 게 있어서 이 커리큐럼을 따라 알고리즘 종류별로 하나씩 공부하는 중이다. '0x'라고 검색한 후 문제집 탭을 클릭하면 쉽게 찾을 수 있다.

 

연결리스트 문제를 다 풀고 오늘은 스택 문제를 풀어볼 차례이다.

요즘 계속 실버 난이도의 문제만 풀다가 골드 문제가 나와서 당황했지만 언제까지 쉬운 문제만 풀 수 없으니 도전!

 

문제

https://www.acmicpc.net/problem/2493

2493번: 탑

 

풀이

역시나 실버 문제들에 비해서 난이도가 꽤 있었다. 스택 문제라는 걸 알고 풀어서 그런지 계속 스택 구조에 대해서 생각하면서 문제를 풀게 됐다. FILO 방식으로 어떻게 문제를 풀 수 있을까를 한참 고민하다가 마땅한 알고리즘을 떠올리지 못 하였다. 결국 일단 기본에 충실하여 이중 for문으로 간단하게 구현하여 채점해보았다.

 

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;

	cin >> n;

	vector<int> tower(n);
	vector<int> receive(n);

	for (int i = 0; i < n; i++) {
		cin >> tower[i];
	}
	
	for (int i = n - 1; i >= 1; i--) {
		for (int j = i - 1; j >= 0; j--) {
			if (tower[i] < tower[j]) {
				receive[i] = j+1;
				break;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		cout << receive[i] << " ";
	}
}

 

예상했던 대로 시간 초과!

n의 크기가 500,000이라서 이중 for문을 돌리면 1.5초는 넘을 거라고 생각했지만 혹시 몰라서 돌려보았다....

 

 

첫 도전을 실패한 후, 예제를 몇 가지 만들어서 새로운 알고리즘을 생각해보았다. 

[6 9 5 7 4], [1 2 3 4 5] [5 4 3 2 1]

이렇게 3가지 예제를 적은 후, 내가 컴퓨터의 방식으로 문제를 푼다면 어떻게 할 것인가, 그리고 필요 없는 값들을 어떻게 제거해야 시간 초과를 해결할 수 있을 것인가 두 가지 방식으로 접근하니 문제가 풀렸다.

만약 tower[i] 값이 tower[i-1] 보다 크다면 tower[i+1] 에게 tower[i-1]은 필요가 없는 값이 된다. 그렇지만 tower[i+2]가 tower[i]보다 크고 tower[i-2]보다 작다면 tower[i+2]에게는 tower[i-2]만이 필요한 값이 되는 것이다.

 

너무 어렵게 설명해놓은 것 같은데, 예제를 통해서 설명하면 [6 9 5 7 4]에서 필요한 값은 [9 7]밖에 없다. 이것이 무엇을 의미하냐면 자신의 오른쪽에 있는 값 중에서 자신이 가장 큰 값만이 필요한 값이라는 것이다.

밑에 그림에서 보면 각 탑이 보낸 레이저 신호가 닿은 탑을 파란 글씨로 적어놨다. 일단 제일 처음 자신의 바로 왼쪽에 있는 탑과 크기를 비교한 후, 왼쪽 탑이 자신보다 크다면 반복을 종료하고, 왼쪽 탑보다 자신이 더 크다면 왼쪽 탑의 레이저 신호가 닿는 탑과 크기를 비교한다. 여전히 자신이 더 크다면 방금 비교한 탑의 수신탑과 또 비교를 한다. 결국 자신보다 큰 탑을 찾거나 큰 탑이 없어 0에 도달하면 반복이 멈춘다.

사실 코드 보는 게 제일 이해 쉬울 듯!

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;
	int j;

	cin >> n;

	vector<int> tower(n+1);
	vector<int> receive(n+1);

	for (int i = 1; i <= n; i++) {
		cin >> tower[i];
	}

	for (int i = 2; i <= n; i++) {
		j = i - 1;
		while (j != 0) {
			if (tower[i] <= tower[j]) {
				receive[i] = j;
				break;
			}
			else {
				j = receive[j];
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << receive[i] << " ";
	}
}