-
2493. [Python]탑Python_알고리즘/Gold V 2023. 2. 6. 21:13
1. 문제
https://www.acmicpc.net/problem/2493
2. 접근 방법
- 시간 제한: 1.5초
- 메모리 제한: 128MB
- 스택
3. 파이썬 코드
# 정답 코드 import sys input = sys.stdin.readline N = int(input()) # 타워들의 리스트를 받아옴 tower_list = list(map(int,input().split())) # 정답을 출력할 리스트 생성 ans_list = [0]*N # stack 리스트 생성 stack = [] # enumerate를 통해서 index 와 value 를 받아옴 for i,v in enumerate(tower_list): # stack 리스트가 존재할경우 반복문 while stack: # stack에 저장된 마지막값과 현재의 value 값을 비교 if stack[-1][1] > v: # stack 값이 더 큰 경우 ans_list의 i 번째 index에 stack의 index 값을 추가 ans_list[i] = stack[-1][0] + 1 break # 그 외의 경우 stack 값을 추출 else: stack.pop() # stack에 i번째 index와 value 값 추가 stack.append([i,tower_list[i]]) print(*ans_list) # 이건 처음 생각해서 틀린 코드 (시간초과) import sys input = sys.stdin.readline N = int(input()) tower_list = list(map(int,input().split())) ans_list = [0]*N for j in range(N-1,-1,-1): ans = tower_list.pop() ans_index = j for i in range(len(tower_list)-1,-1,-1): if tower_list[i] > ans: ans_list[j] = i+1 break else: ans_list[j] = 0 print(*ans_list)
4. 문제를 풀고난 후 생각
- 처음 접근한 방식은 오른쪽부터 시작해서 큰값이 있는지를 체크하는 방식으로 코드를 구현하였고 오른쪽에서 부터 pop을 해가며 탐색하는 것이였다.
- 스택을 제대로 이해한 것이 아니여서 스택이라 생각하고 풀었지만 막상 실제로 풀었던 코드는 완전탐색과 거리가 가까운 코드였다.
- 이후 다른 사람들의 풀이를 보며 생각했고, 거꾸로 탐색해 나가는 것이 아니고 처음부터 stack에 쌓아가며 값들을 비교하는 식으로 진행하면 한번의 반복문으로도 해결이 가능했고 시간초과도 나지 않는다.
5. 문제를 푸는데 도움이 되는 지식
- 스택
'Python_알고리즘 > Gold V' 카테고리의 다른 글
7576. [Python]토마토 (0) 2023.09.17 1334. [Python]다음 팰린드롬 (0) 2023.09.17 1038. [Python]감소하는 수 (0) 2023.09.08 1083. [Python]소트 (0) 2023.09.07 5430. [Python]AC (0) 2023.08.08