[스택] 백준 2493번 (C언어) : 탑

#include<stdio.h>

int tower[500001];
int result[500001];

int main()
{
    int num;
	tower[0] = 100000001;

	scanf("%d", &num);

	for (int i = 1; i <= num; i++)
		scanf("%d", &tower[i]);
	

	for (int i = 1; i <= num; i++)
	{
		for (int j = i - 1; j >= 0;)
		{
			if (tower[j] >= tower[i])
			{
				printf("%d ", j);
				result[i] = j;
				break;
			}
			else
				j = result[j];
		}
	}
	return 0;
}

위 문제는 스택을 써서 풀어야 한다고 했지만, 일단 스택을 생각하지 않고 먼저 c언어로 구현해 보았습니다.

일단 탑의 높이를 받아줄 배열 하나와 최종 값에 대한 배열 하나를 생성합니다.

for문을 살펴보면 일단 현재 인덱스를 가리키는 i와 이전의 인덱스를 가리키는 j가 있습니다.

만약 이전의 탑이 이후의 탑보다 높다면 j를 출력하고 result 배열에 i번째 인덱스에 j를 넣습니다. else의 경우에는 그냥 j번째 인덱스가 j가 됩니다.

 

이를 좀 더 단적으로 해석해 보면 문제의 예시처럼 6, 9, 5, 7, 4가 있습니다. 먼저 6을 봅니다. i가 1부터 시작하기 때문이죠. 이전에 tower [0]의 값을 큰 수로 설정했는데 그 이유는 무조건 첫 타워는 0이 도출되기 때문입니다. 6이 더 작기 때문에 if문이 실행되고, result의 i번째 인덱스인 1에 j인 0이 저장됩니다. 

그다음에 9는 6보다 크기 때문에 else가 적용됩니다. else가 적용되면 이미 모든 인덱스가 0으로 초기화되어 있기 때문에 j의 값을 0으로 초기화시킵니다. 그 다음에 5는 9보다 작기 때문에 result의 2번째 인덱스에 j의 값인 2를 넣습니다. 

다음은 7은 5보다 크기 때문에 if가 실행됩니다. 나머지는 위의 과정을 따라갑니다.

 

출력에서는 print를 먼저 해주기 때문에 인덱스 순서와 출력은 무관합니다. result의 인덱스는 tower [0] 때문에 한 칸씩 뒤로 밀려서 값이 들어가게 됩니다. 그러나 그전에 출력을 해주기 때문에 밀린 인덱스의 영향을 받지 않고 출력이 되는 것입니다.