백준 : 2493번, 탑

문제 주소 : www.acmicpc.net/problem/2493

정답 비율 : 29.235% (2021.02.10 20:30 기준)

2493번: 탑

 

문제 요약 :

n 개의 숫자가 주어집니다. 주어진 숫자 index에 대하여 이전 index에서 현재 숫자보다 이상인 숫자 중에서 가까운 숫자의 index를 출력하는 문제입니다. 자신보다 큰 숫자가 없을 경우 0을 출력합니다.

ex) 6 9 5 7 4

6(index : 1) 입장에서 자신보다 작은 index에서 큰 숫자가 없으므로 0을 출력합니다.

9(index : 2) 입장에서 자신보다 작은 index에서 큰 숫자가 없으므로 0을 출력합니다.

5(index : 3) 입장에서 자신보다 작은 index에서 큰 숫자는 6과 9가 있으므로 가장 가까운 9의 index인 2를 출력합니다.

7(index : 4) 입장에서 자신보다 작은 index에서 큰 숫자는 9만 존재하므로 9의 index인 2를 출력합니다.

4(index : 5) 입장에서 자신보다 작은 index에서 큰 숫자는 6, 9, 5, 7가 존재합니다. 따라서 가장 가까운 7의 index인 4를 출력합니다.

최종 출력 : 0 0 2 2 4

 

문제 조건 :

입력 : n의 범위는 1 이상 500,000 이합니다. 주어지는 숫자의 범위는 1 이상 100,000,000 이하입니다.

출력 : index 사이에 하나의 공백을 두고 출력합니다. 자신 이상의 숫자가 없을 경우 0을 출력합니다.

시간 : 1.5초

 

문제 풀이

문제 해석하면서 이해하면서 가장 먼저 떠오른 생각은 아주 비효율적이지만 전수 조사하는 방법이었습니다.

 

#include<stdio.h>

int arr[500001];

int main()
{
	int num = -1, i = -1, j = -1;

	scanf("%d", &num);

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

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

-> 현재 index보다 작은 index를 일일이 조사하여 index를 알아내는 것이었습니다.

 

시간제한 1.5초 이기에 전수 조사해도 될 거라고 생각하였지만 51%까지 아슬아슬하게 가다가 결국 시간 초과하였습니다.

 

이어서 떠오른 것은 DP를 사용하는 것이었습니다. (자세한 설명은 접은 글 참조 바랍니다.)

9 1 2 7 4 8과 같은 데이터가 있을 때 

-------------------

초기

DP : 0 0 0 0 0 0

AR : 9 1 2 7 4 8

-------------------

9를 연산합니다. 9 입장에서는 왼쪽에 숫자가 없으므로 0을 출력합니다. DP는 0으로 유지합니다.

-------------------

9계산 후

DP : 0 0 0 0 0 0

AR : 9 1 2 7 4 8

-------------------

1을 연산합니다. 1은 9와 비교를 합니다. 9보다 작으므로 9의 index인 1을 출력합니다. DP는 1로 바꿉니다.

-------------------

1계산 후

DP : 0 1 0 0 0 0

AR : 9 1 2 7 4 8

-------------------

2를 연산합니다. 2는 1과 비교합니다. 1은 2보다 작으므로 1의 dp의 index인 9과 비교합니다. 9보다 작으므로 9의 index인 1을 출력합니다. DP는 1로 바꿉니다.

-------------------

2계산 후

DP : 0 1 1 0 0 0

AR : 9 1 2 7 4 8

-------------------

7을 연산합니다. 7은 2과 비교합니다. 2는 7보다 작으므로 2의 dp의 index인 9과 비교합니다. 9보다 작으므로  9의 index인 1을 출력합니다. DP는 1로 바꿉니다.

-------------------

7계산 후

DP : 0 1 1 1 0 0

AR : 9 1 2 7 4 8

-------------------

4를 연산합니다. 4는 7과 비교합니다. 7은 보다 크므로 7의 index인 4를 출력합니다. DP는 4로 바꿉니다.

-------------------

7계산 후

DP : 0 1 1 1 4 0

AR : 9 1 2 7 4 8

-------------------

8을 연산합니다. 8은 4과 비교합니다. 4는 8보다 작으므로 4의 dp의 index인 7과 비교합니다. 7도 8보다 작으므로 7의 dp의 index인 9과 비교합니다. 8은 9보다 작으므로 9의 index인 1을 출력합니다.

-------------------

8계산 후

DP : 0 1 1 1 4 1

AR : 9 1 2 7 4 8

-------------------

 

-> 확실히 전수 조사보다는 효율적으로 돌아가는 것을 확인할 수 있습니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int DP[500001];
int AR[500001];

int main()
{
	int num = -1, i = -1, j = -1;
	AR[0] = 100000001;

	scanf("%d", &num);

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

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

 

 

C언어로 작성 후에 python으로 어떻게 작성하지 하며 고민할 때 해당 문제의 분류가 자료구조, 스택 임을 확인하였습니다. 따라서 python의 경우에는 stack을 이용하여 풀기로 하였습니다.

 

문제의 분류가 stack이라는 것은 push과 pop의 조건을 생각하면 되었습니다. 위에 DP를 이해하면 쉽게 떠올릴 수 있습니다. 따라서 고민 후에 접은 글 확인해보는 것도 좋겠습니다.

push의 조건 : 스택이 비어있거나, 스택이 top이 자신보다 클 때입니다.

pop의 조건 : 스택 top의 값이 자신보다 작으면 pop을 진행합니다.

 

-> 저의 한계로는 생각할 수 있는 최선의 방법입니다. 혹시 다른 방법이 존재하면 댓글로 부탁합니다.

 

Python3

#solve 2493

num = int(input())
num_list = [int(i) for i in input().split()]
stack = []

for i in range(0, num):
    while(1):
        if len(stack) == 0:
            print("0 ", end="")
            stack.append([i, num_list[i]])
            break
        
        if stack[len(stack)-1][1] >= num_list[i]:
            print(stack[len(stack)-1][0] + 1, end=' ')
            stack.append([i, num_list[i]])
            break
        else :
            stack.pop()

 

 

문제 분류를 보니 한국 정보올림피아드 지역 본선 2009 초등부 4번 문제라고 명시되어 있는데 ㄷㄷ 좀 더 많은 공부와 노력이 필요하다는 것을 느꼈습니다.