[백준] 2493 탑 - python

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

2493번: 탑

골드인데 할만해보여서 덤볐다가 교수님과 2시간 잡고 있었다.

무지랭이를 도와주시려고 계속 옆에서 알려주신 교수님께 이영광을

 

내가(교수님의도움을받아^^) 푼 코드

num = int(input())
li = list(map(int,input().split()))
temp = []
ans =[]

for j in range(len(li)):
    # 첫번째 숫자는 무조건 0
    flag = True
    for i in range(j-1, -1, -1):
        if li[i] > li[j]:
            flag = False
            ans.append(i+1)
            break
    if flag:
        ans.append(0)
 
print(*ans)

li의 인덱스보다 인덱스가 작은 값들과 계속 크기를 비교하고,

li[i]보다 앞 인덱스에서 값이 큰 수가 있으면, 그 수의 인덱스+1을  ans에 추가하는 방식

만약 이 반복문에 들어가지 않았다 = 앞 인덱스에 더 큰 숫자가 없었다면 ans에 0을 추가

굉장히 간단해보이는 코드지만 여기까지 오는데 정말 힘들었따

그러나 골드는 골드였다

시간초과에 바로 걸려버린 ^^

 

그래서 찾아봤더니 그냥 stack으로 푸는 문제였다.

stack문제만 하루종일 풀어놓고, stack 쓸 생각을 안하다니 난 정말 밥오다

 

1. stack에 아무것도 없을 때,  li[i]를 추가한다

2. li[i]와 stack의 가장 마지막 값의 크기를 비교한다

3. if li[i]가 더 크다면 -> stack의 마지막 값을 제거 + stack에 li[i] 값을 추가

else stack의 마지막 값이 li[i]보다 크다면 -> stack에 li[i]를 추가 + ans에 (더 컸던 수의 index+1)을 추가

4. stack이 비어있으면 항상 li[i]를 stack에 추가함

num = int(input())
li = list(map(int,input().split()))
stack = []
ans = [0]*num
for i in range(num):
    if stack :
        while True:
            if li[i] <= stack[-1][0]:
                ans[i] = stack[-1][1] + 1
                stack.append([li[i], i])
                break
            else : 
                stack.pop()
            if not stack :
                stack.append([li[i], i])
                break
    else:
        stack.append([li[i], i])

print(*ans)

이해가 잘안되서 하나하나 손으로 써가면서 이해하려구 노력함 . .

i = 0

stack=[6]

ans = [0, 0, 0, 0, 0]

 

i = 1

stack = [6]

9 > stack[-1] -> stack.pop() -> stack.append(9)

stack = [9]

ans = [0, 0, 0, 0, 0]

 

i = 2

stack = [9]

5 < stack[-1] -> stack.append(5) -> ans[i].append(9의 인덱스 + 1)

stack = [9, 5]

ans = [0, 0, 2, 0, 0]

 

i = 3

stack = [9, 5]

7 > stack[-1] = 5 -> stack.pop()

stack = [9]

7 < stack[-1] = 9 -> stack.append(7) -> ans[i].append(9의 인덱스 +1)

stack = [9, 7]

ans = [0, 0, 2, 2, 0]

 

 

i = 4

stack = [9, 7]

4 < stack[-1] = 7 -> stack.append(4) -> ans.append(7의 인덱스 + 1 )

stack = [9, 7, 4]

ans = [0, 0, 2, 2, 4]

 

손으로 써봤지만, 역시 아직 내 머리만으로 이걸 이해하기에는 어려운 것 같다.

stack 공부를 좀 더해야할듯하다

역시 gold의 벽은 높다 . .

 

 

 

참고한 블로그

https://fre2-dom.tistory.com/201

[baekjoon] 백준 2493번(파이썬): 탑