백준 2493

백준에서는 분류가 스택으로 되어있었는데 도저히 스택으로는 답이 보이지 않아서 다른 방식으로 풀었다.

 

1. data, res 라는 2개의 배열을 만든다.

2. data 배열에는 input값(탑들의 높이)을 저장한다.

3. res에는 해당 탑의 레이저를 송신받는 탑의 번호를 저장한다.

res에 저장되는 탑의 번호는 0부터 시작한다고 가정하였다. 

4. 현재 탑의 높이를 앞의 탑의 높이와 비교한다. 만약 앞의 탑의 높이가 더 낮다면 앞의 탑의 레이저를 송신받는 탑의 높이와 비교한다.

 

 

예를 들어,

---

6

10  5  6  7  11  8

---

이렇게 input이 들어온다면 

 

6번째 탑의 높이는 8이므로 5번째 탑이 레이저 송신을 받을 것이다.

따라서 data[5] = 8, data[4] = 11, res[5] = 4 가 될 것이다. 

 

→ 순서대로 탑의 높이를 앞의 탑의 높이와 비교하면 1번째 탑은 송신받을 탑이 없다.

따라서 res[0] = -1 이 될 것이다.

 

→ 2번째 탑은 1번째 탑이 송신받을 수 있으므로 res[1] = 0 가 된다.

 

→ 3번째 탑은 2번째 탑이 송신받을 수 없으므로 res[1]에 저장되어있는 값을 확인하고, 이 경우 0이 저장되어 있기에 1번째 탑의 높이와 비교한다.

10 > 6 이므로 res[2] = 0 이 된다.

 

→ 4번째 탑은 3번째 탑이 송신받을 수 없으므로 res[2]에 저장되어있는 값을 확인하고, 이 경우 0이 저장되어 있기에 1번째 탑의 높이와 비교한다.

10 > 7 이므로 res[3] = 0 이 된다.

 

→ 5번째 탑은 4번째 탑이 송신받을 수 없으므로 res[3]에 저장되어있는 값을 확인하고, 이 경우 0이 저장되어 있기에 1번째 탑의 높이와 비교한다.

10 < 11 이므로 res[0]에 저장되어있는 값을 확인한다.

이 경우 -1이 저장되어 있기에 더이상 비교할 수 있는 탑이 없으므로 res[4] = -1 이 된다.

 

답을 출력해줄때는 res에 저장된 값들에 1씩 더해줘서 출력해주어야 한다.

 

예시 코드

import sys

N = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

res = [-1 for i in range(N)]
for i in range(1, N):
    idx = i-1
    x = data[idx]
    while(x < data[i]):
        idx = res[idx]
        x = data[idx]
        if(idx == -1): break;
    res[i] = idx

for i in res:
    print(i+1, end=' ')