2493 탑

아이디어

이 문제가 왜 스택 문제인가?를 고민해야 아이디어가 보이는 문제.
탑이 맨 처음 것부터 하나하나 새로 들어온다고 생각하고 보면 아이디어가 보인다.
새로 탑이 지어질 경우, 만약 그 앞에 있는 탑이 새로 지어진 탑보다 작다면? 그 탑은 레이저를 맞을 일이 없게 된다 (새 탑이 가리니까)
이 점을 이용하여, 탑을 스택에 넣고, 스택 맨 위의 탑이 새로 들어올 탑보다 작다면 그 탑을 내보내는 작업을 반복하면 되겠다는 아이디어를 냈음.

구현

제출 1 (시간 초과)

import sys

input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))
stack = [0]

for tower in towers:
    while stack[-1] <= tower:
        stack.pop()
        if stack == []:
            print(0, end=" ")
            stack.append(tower)
            break
    else:
        print(towers.index(stack[-1]) + 1, end=" ")
        stack.append(tower)

‼️ 시간 초과의 원인 - index 함수

index 함수는 리스트를 전부 돌면서 해당하는 값의 인덱스를 찾아냄 : O(n)
따라서 O(n) 짜리 반복문 안에서 사용 시 바로 O(n^2)가 되어버린다. 조심!!

그렇다면 index 함수를 쓰지 않고도 인덱스를 찾아낼 수 있어야 한다.. 대안을 찾았다.

제출 2 (정답)

import sys

input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))
stack = [0]

tower_idx_finder = {v: i for i, v in enumerate(towers)}

for tower in towers:
    while stack[-1] <= tower:
        stack.pop()
        if stack == []:
            print(0, end=" ")
            stack.append(tower)
            break
    else:
        print(tower_idx_finder[stack[-1]] + 1, end=" ")
        stack.append(tower)

index 함수 회피 방법 -> 딕셔너리 사용, value를 키, 인덱스를 값으로

이 아이디어를 적용했더니 문제가 바로 풀렸다.
하지만 그때는 몰랐던 것이 있었으니...

여담 : 사실 이 회피 방법은 완전한 방법이 아님

‼️ value를 키로 사용하기 때문에, value에 중복된 값이 있으면 제일 마지막에 할당한 인덱스로 덮어쓰게 됨!

우연히 이번 문제는 높이가 같은 탑이 있을 경우 맨 오른쪽 탑에 레이저가 맞기 때문에 정답이 나올 수 있었다.
다른 회피 방법이 있을지는.. 계속 풀면서 생각해야겠다.