백준-2493 탑

문제 😁

왼쪽방향으로 레이저를 쏘는 탑이 자기보다 큰 탑에만 레이저가 도달한다. 입력되는 탑의 길이에 맞게 수신되는 탑의 번호를 출력하라

문제 자체는 어렵지않다.

방법 🤣

1. 첫번째 방법

이문제는 스택문제로 당연히 O(n2)을 하면 시간초과로 오류가 나온다.
(완전탐색)

2. 두번째 방법

스택을 이용.
그치만 이제 불완전함

import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

result = []
stackArr = []

for i in range(len(arr)):
  if i == 0:
    stackArr.append([i, arr[i]])
  else:
    for j in range(len(stackArr)-1, -1, -1):
      if arr[i] > stackArr[j][1]:
        stackArr.pop()
    stackArr.append([i, arr[i]])

  if len(stackArr) == 1:
    result.append(0)
  else:
    result.append(stackArr[-2][0] + 1)

for i in range(len(result)):
  print(result[i], end=' ')

스택을 이용해서 최대한 시간을 줄여보려했다.
나는 정말 잘했다 생각했는데 계속 69퍼, 65퍼에서 시간초과로 안되길래 이걸로 정말많이 고민했다.

(엄청 틀렸다.. 다음장도 틀렸습니다, 시간초과 천지임.)

이 방법은 스택을 사용한건 잘했는데 stack의 원소가 많아지면 그 stack을 계속 순회하므로 좋지는 못하다.

탈락

3. 마지막 방법

import sys

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

result = []
stackArr = []


for i in range(len(arr)):
  while stackArr:
    if arr[i] < stackArr[-1][1]:
      result.append(stackArr[-1][0] + 1)
      break;
    stackArr.pop()

  if not stackArr:
    result.append(0)
      
  stackArr.append([i, arr[i]])



for i in range(len(result)):
  print(result[i], end=' ')

스택을 이용한건 2번째 방법과 같으나 가장 큰 차이점은 break의 여부라 생각한다. 2번째는 stack에 계속 마지막 stack보다 작은녀석이 들어온다면 예를들면 100000, 99999, 99998 ... 1씩계속 들어와서 1까지들어오면다면 stack에 쌓일 거고 for loop로 매 반복문마다 한바퀴를 돌고 result에 값을 넣는다.

3번째 방법은 그러지 않고 우리의 목적은 result이니 result에 값을 넣으면 break을 걸어서 불필요한 반복을 줄였다.(2번에서도 for사용하면서 break을 사용하려 했지만 설계를 하던거랑달라서 어려웠음..)

느낀점 😀

• 스택에 대해 오래 고민해보는 점이 좋았다.
• 한방법이 안되면 여러방법을 생각해보자