[알고리즘/자료구조] 2493번 : 탑 - python

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

 

 

---

• 문제
• 소요시간: 40분 10초(부분 실패)

---

• 설계하기(접근방법) 

1. 입력받기

타워의 높이를 입력받는다

 

2. 구현하기

처음에는 탑의 위치를 지정해가면서 순회했으나 시간초과가 났다.

방법이 떠오르지 않아 카테고리를 확인했고, 스택을 쓰는 문제였다는 것을 확인할 수 있었다

 

따라서 스택으로 코드를 구현했다

자기보다 작은 높이가 스택에 있는 경우, 자기보다 큰 높이가 나올때 까지 pop해준다

즉 큰 높이를 마주했을 때가 레이저를 마주했을 때와 같다.

그 후 자신의 높이를 stack에 append 해준다.

 

stack이 비어있거나, 자신보다 큰 높이를 찾지 못한 경우, 0을 저장해주고

자신을 스택으로 append한다

 

3. 출력하기

저장한 laser의 위치를 출력한다

 

---

• 코드(출력)

n = int(input())

tower = list(map(int, input().split()))

stack = [[tower[0],0]]
laser = [0]

for i in range(1, len(tower)):
        if tower[i] > stack[-1][0]:
            while stack and stack[-1][0] < tower[i]:
                a = stack.pop()
            stack.append([tower[i],i])
            # stack에 현재보다 큰 것이 없었을 때
            if len(stack) == 1:
                laser.append(0)
            # 스택에 현재보다 큰 것이 있는 경우
            else:
                laser.append(stack[-2][1] + 1)
        else:
            stack.append([tower[i],i])
            laser.append(i)

print(*laser)

---

• 얻어갈 부분

1. 자료구조를 떠올렸으나 스택을 사용하는 방법을 떠올리지 못했다. 레퍼런스로 꼭 가지고 있자