[ BOJ / 파이썬 ] 2493 탑

이 문제가 스택 유형이라는 것을 알고 있어서 쉽게 풀 수 있을 것 같다는 생각을 했다.

혼자였으면 스택이라는 것도 파악 못 할 뻔 했어서 그걸 아니까 조금 자신감이 생긴 느낌이었다.

 

/  제출 1  /

import sys
input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))

result = []
while towers:
  current = towers.pop()
  remains = len(towers)
  while remains > 0:
    if towers[remains-1] >= current:
      break
    remains -= 1
  result.append(remains)

while result:
  print(result.pop(),end= " ")

: 시간 초과

 

: 테스트 케이스는 괜찮은데, 탑 개당 퇴대 높이가 100,000,000개(1억 개)에다가 최대 탑의 개수가 500,000(50만)개였다.

: 저렇게 일일히 다 계산하면 백퍼 시간에 걸린다. 아 어떻게 개선하지..  이 문제가 골드인 이유가 있네.

 

 

 

/ 제출 2  /

import sys
input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))

result = []
while towers:
  current = towers.pop()
  remains = len(towers)
  # 수정부분
  if towers and max(towers) < current:
    result.append('0')
    continue
  # .
  while remains > 0:
    if towers[remains-1] >= current:
      break
    remains -= 1
  result.append(str(remains))

# 수정부분
result.reverse()
print(" ".join(result))
# .

1. 만약 검사할 대상 중에 나보다 큰 애가 없다면 검사할 필요가 없으므로 바로 0을 넣게 했다.

2. 마지막 result를 하나하나 뽑을 게 아니라 뭉텅이로 join하면 내부적으로 더 빨리 돌지 않을까해서 그런 식으로 고쳤다.

 

=> 그래도 시 간 초 과

 

안 건드린 while문 부분에서 하나하나 검사하면서 문제가 생기는 것 같다. 역시. 어떻게 수정해야할까 ㅠ

 

 

다른 분들 풀이를 보니 내 방향성과 다르다.

나는 뒤에서부터 판별하려고 한 생각을 벗어나지 않았다. 그런데 다른 풀이들은 첫 번째 수부터 차례대로 체크해나가며 자기 앞의 값만 비교한다. 자기 앞의 값들은 그리고 줄여준다. 이걸 스택을 이용해 구현한다. 

 

https://www.acmicpc.net/board/view/70952#comment-117675

글 읽기 - [ python ] 정답코드와 시간초과 코드의 차이점을 알려주세요!!!

https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0%EC%83%81%ED%99%98%EB%B6%84%EC%84%9D

분할상환분석 - 위키백과, 우리 모두의 백과사전

 

 

import sys
input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))
stack = [[1, towers[0]]] # 맨 앞 답에 닿는 애들
result = [0]

for i in range(1, n):
  while stack:
    if stack[-1][1] >= towers[i]:
      result.append(stack[-1][0]) # 내 앞의 걔가 내 답
      stack.append([i+1, towers[i]]) # 나도 걔에 묶여서 쌓여 일단
      break
    else: # 만약 내 앞의 애가 내가 닿을 지점이 아니야. 그러면 걔 빼, 그리고 다음 턴에서 그 앞의 애 검사
      stack.pop() # 어차피 이 pop되는 애가 닿는 지점은 저장되어 있어서 그냥 버리기만 하면 됨.
  if not stack:
    # 내 앞에 쭉 뺐는데도 내 답(내가 닿을 애)를 찾지 못했다면
    result.append(0)
    stack.append([i+1, towers[i]]) #내 값 스택에 넣긴 넣어야지

print(" ".join(map(str, result)))

: 호우.. 어렵당.. 

: 그러니까 스스로 stack에 들어갈 값을 잘 정의해야한다.

: stack에 왜 넣는지, 이걸 해서 어떤 효과가 나는지 생각해보기.

 

: 일단 이 문제 같은 경우는 내 앞 애들 중에 가까운 순서대로 체크하고 그 다음애 검사하니까 스택으로 검사대상들을 모아줬다.

: 그리고 결과값은 스택에 넣는 순간에 내 값을 기준으로 저장한다. 빼는 순간이 아니라. 이거 전에 BFS인가할 때도 넣는 순간이냐, 빼는 순간이냐에 따라 값이 바뀌는 경우가 있었다. 항상 시점에 신경 쓰자.

 

: 그리고 특히 이 문제는 생각의 관점이 중요하다. 내 앞의 대상값이 될 애들을 어떻게 최소화할 지.. 

 

: 배움이 많은 문제였다.