알고리즘 문제풀이
- 문제 : 탑
- 해결 : 시간초과
- 분류 : 스택
초기 풀이방법(시간초과)
- 탑 길이들의 배열을 for문으로 돌면서 하나씩 pop한다
- 각 탑의 길이보다 짧은 요소들은 smaller 스택에 넣는다
- 계속 pop하면서 더 긴 요소를 찾으면 smaller 스택에 있는 요소들을 다시 원래 리스트에 이어 붙인다.
- 더 긴 요소의 인덱스를 결과 배열에 저장한다.
시간 초과 이유 : 해당 요소보다 더 작은 요소들은 그냥 pop해버리고 따로 저장해두지 않아도 된다. 그런데 따로 저장해두고 다시 이어 붙이는 과정이 있어서 시간초과가 발생했다.
개선 풀이방법
- 각 요소들을 for문으로 순회한다. 처음부터
- 스택에는 이전 요소들의 값들이 저장되어 있다.
- 스택에 아무것도 없다면 0 출력
- 스택에 요소가 존재한다면 자신보다 작은 요소들은 pop하여 없앤다. 큰 요소가 존재할 경우 해당 인덱스 출력
- 현재 요소를 스택에 push
소스코드
N = int(input())
H = list(map(int, input().split()))
stack = []
for i in range(N):
while stack:
top = H[stack[-1]]
if top > H[i]:
break
stack.pop()
if stack == []:
print(0)
else:
print(stack[-1]+1)
stack.append(i)왜 스택 자료구조를 이용해야되는지
문제에서 레이저는 왼쪽으로만 발사된다고 했다. 즉 방향이 하나뿐이다.
해당 노드 기준으로 왼쪽에 있는 노드들 중에서 가장 가까운 큰 노드가 정답이 된다. 스택의 경우 가장 최신의 노드 (=거리가 가까운 노드)가 최상위 노드에 있다. 또한 스택은 순서가 유지된다.
느낀 점
- 스택을 사용함으로써 어떤 점을 활용할 수 있는지 모르겠다.
- 어떤 경우에 스택을 사용해야하는지
- 문자열, 괄호열 처럼 특정한 한 방향으로 순서가 이루어질 때 스택을 사용한다는 건 알겠는데 내가 스택의 특성을 잘 활용하지 못하고 있는 것 같다.
녁므