[ 파이썬(python) ] 백준 2493 - 탑

📍 백준 2493 - 탑

문제: 백준 2493 - 탑

---

💡 나의 풀이

스택을 활용하면 되는 문제인데 머릿속으로는 단계별로 생각이 잘 됐는데 코드로 구현하려니까 쉽지 않았다. 우선 범위가 500,000이기 때문에 이중 반복문을 사용하면 최대 250,000,000,000까지임을 명심해야 한다. 여기서 의문점은 성공코드와 실패 코드의 시간 복잡도의 차이는 (index, slicing)의 차이인것 같은데 왜 시간초과가 나는지 잘 모르겠다.(고수님들 댓글부탁드립니다 :))

 

---

[ 21. 7. 13. ]

백준에 시간초과 관련하여 질문을 남겼는데 @djm03178님께서 좋은 답변을 해주셨다. 결론적으로 시간복잡도는 다음과 같다.

 

1. 성공코드(O(N)): 각 원소가 스택에 들어가고 나오는 연산이 한 번씩만 수행된다.

2. slicing(O(N^2)): 각 원소마다 `slicing`을 수행하는데 대상 원소의 수가 1부터 `N`까지 계속 증가하고 `slicing`의 시간복잡도는 원소의 수와 비례하므로 `O(N^2))`이 된다.

3. index(O(N^2)): 각 원소마다 `index`함수가 해당 원소를 찾기 위해 리스트를 처음부터 끝까지 순회하기때문에 역시 `O(N^2))`가 된다.

 

두번째 세번째 코드는 이해가 잘 됐으나 첫번째 코드가 왜 `O(N)` 인지 이해가 안돼서 질문을 남겼더니 다음과 같은 답변을 받았다.

 

" 첫번째 코드에서 이중 반복문을 각각 최악의 경우 `O(N)`번씩 돈다고 생각해서 `for * while = O(N^2)` 이라고 판단하면 안된다. 만일 바깥 루프가 한번 돌 때 운이 안 좋아서 안쪽 루프의 `N`개의 원소를 pop했다고 가정하면, 그 한번의 루프를 제외한 나머지는 모두 `pop`을 안했다는 것이다.(while stack: 조건때문에) 즉, 아무리 루프를 오래 돌리려고 해도 안쪽 루프가 N번보다 많이 돌 수 는 없다.

 

언젠가 많이 돈 때가 있다면, 다른 때는 많이 안 돌았어야만 하고 총 횟수 역시  `O(N)`밖에 안된다. 즉, 안쪽 루프가 도는 총 횟수를 다 합했을 때 `O(N)`이라는 큰 그림을 보는게 중요하지, 바깥 루프가 한 번 돌때 안쪽 루프가 최대 `O(N)`번 도는 그림은 볼 필요가 없다는 뜻이다. 이 코드의 최악의 경우에도 전체가 `O(N)`이다. "

 

라고 답글을 달아주셨는데.. 굉장히 멋있으셨다. 나도 열심히 공부해서 저분처럼 답글을 달아줄 수 있는 날이 왔으면 좋겠다. 답변과 함께 분할상환분석 링크도 주셨는데 한번 살펴봐야겠다. 

---

 

실패 코드는 뒤에서부터 비교했고 성공코드는 앞에서부터 비교했다. 성공코드의 풀이 방법을 보자.

 

1. stack이 존재하는 동안에 이전에 들어온 stack[-1][1]의 값과 지금 들어올 top[i]의 값을 비교한다.
2. 만약, 이전에 들어온 stack[-1][1]의 값이 top[i] 보다 크면 레이저 신호를 수신할 수 있기 때문에 그때의 stack[-1][0](index)를 저장한다.
3. 그렇지 않으면, 다음으로 존재하는 stack값을 확인하기 위해 pop()한다.
4. stack에 아무것도 남지 않으면 [i, top[i]]값을 넣는다.(이때, i를 넣는 이유는 index를 저장하기 위함이다.)

 

이해가 잘 안 되면 다음 사진을 보자.

 

 

# 성공 코드
n = int(input())
top = list(map(int, input().split()))
stack = []
answer = [0 for i in range(n)]

for i in range(n):
    while stack:
        if stack[-1][1] > top[i]:
            answer[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()
    stack.append([i, top[i]])

print(*answer)

 

n = int(input())
top = list(map(int, input().split()))
index = [0] * n

# 시간 초과 코드: slicing 함수 사용
for i in range(1, n):
    stack = top[:n - i]
    index_value = len(stack)

    while stack:
        if stack[-1] > top[n - i]:  # 현재 값보다 탑이 더 크면
            high_top = stack[-1]
            index[n - i] = index_value
            break
        else:    # 현재 값보다 탑이 작거나 같으면
            index_value -= 1
            stack.pop()

# 시간 초과 두번째 코드: index 함수 사용
for i in range(1, n):
    stack = top[:n-i]

    while stack:
        if stack[-1] > top[n-i]:    # 현재 값보다 탑이 더 크면
            high_top = stack[-1]
            index[n-i] = top.index(high_top) + 1
            break
        else:
            stack.pop()

print(' '.join(map(str, index)))