[백준 추천문제] 22866번 - 탑 보기

문제: https://www.acmicpc.net/problem/22866

이 문제는 좀 신박했던거 같아서 공유해보고 싶어서 써봅니다.

문제 접근하기

처음 이 문제를 보고 예전에 풀었던 물 채우기(?) 문제가 생각났습니다. 단순하게 그거랑 같은 문제인데 예시만 다른건가 싶었습니다. 근데 곰곰히 생각해봐도… 그 문제랑은 좀 다른거 같았습니다.

무식하게 풀어볼까도 생각했지만 o(n^2)가 될 거 같아서 시간초과가 날 거 같았습니다. 예를 들어, 다 동일한 높이인 경우 혹은 그와 비슷하게 일부만 높이가 높고 혹은 낮고, 다 비슷한 경우 문제가 될 거라 생각 되었습니다.

풀이 참고

어쩔 수 없이 어떤 알고리즘으로 풀어야 하는지 봤는데 전혀 생각지도 못한 스택이 나왔습니다. 결국 해답을 보고 말았는데…

• https://nahwasa.com/entry/백준-22866-자바-탑-보기-BOJ-22866-JAVA?category=1049955?category=1049955 (풀이 위주로 볼 것)
• https://velog.io/@tunaman95/백준-22866번-탑-보기-Python (코드 위주로 볼 것)

와.. 생각의 전환이 좀 필요했었습니다. 하나는 처음부터 끝까지 진행하고, 또 하나는 반대로 끝에서부터 처음까지 진행을 하면서 건물마다 좌측과 우측에서 볼 수 있는 건물의 수와 해당 건물과 가장 가까운 거리의 번호가 작은 건물 번호를 계산할 수 있었습니다. 이건 도저히 생각치 못한 방법이었네요…

풀이 코드

참고 : https://github.com/ckstn0777/Python-Algorithm-Pratice/blob/main/backjoon/data_structure/22866.py

if __name__ == "__main__":
    n = int(input())
    l_list = list(map(int, input().split()))

    cnt = [0] * (n + 1) # i번째 건물이 볼 수 있는 다른 건물의 수
    near = [[int(1e9), int(1e9)] for _ in range(n + 1)] # [가장 가까운 건물번호, 가장 가까운 건물거리]


    # 처음부터 순차적 진행 : 해당 건물에서 좌측기준 볼 수 있는 건물이 스택에 들어가게 됨
    stack = []
    for idx, v in enumerate(l_list, 1):
        # stack pop 조건 - 데이터가 있고, 스택 최상위 건물의 높이가 현재 건물 높이와 같거나 작으면 더 이상 안보이기 때문에 제거
        while len(stack) > 0 and stack[-1][1] <= v:
            stack.pop()
        cnt[idx] += len(stack) # 해당건물기준 좌측으로 볼 수 있는 건물 수 

        if len(stack) > 0:
            dist = abs(stack[-1][0] - idx) # 해당 건물기준 가장 가까운 좌측건물과의 거리
            if dist < near[idx][1]:
                near[idx][0] = stack[-1][0]
                near[idx][1] = dist
            elif dist == near[idx][1] and stack[-1][0] < near[idx][0]: # 거리는 같은데 건물번호가 더 작은 경우
                near[idx][0] = stack[-1][0]

        stack.append([idx, v]) # 건물번호와 높이
    
    # 반대로 진행 : 해당 건물에서 우측기준 볼 수 있는 건물이 스택에 들어가게 됨
    stack = []
    for idx, v in reversed(list(enumerate(l_list, 1))):
        # stack pop 조건 - 데이터가 있고, 스택 최상위 건물의 높이가 현재 건물 높이와 같거나 작으면 더 이상 안보이기 때문에 제거
        while len(stack) > 0 and stack[-1][1] <= v:
            stack.pop()
        cnt[idx] += len(stack) # 해당건물기준 우측으로 볼 수 있는 건물 수 

        if len(stack) > 0:
            dist = abs(stack[-1][0] - idx) # 해당 건물기준 가장 가까운 우측건물과의 거리
            if dist < near[idx][1]:
                near[idx][0] = stack[-1][0]
                near[idx][1] = dist
            elif dist == near[idx][1] and stack[-1][0] < near[idx][0]: # 거리는 같은데 건물번호가 더 작은 경우
                near[idx][0] = stack[-1][0]

        stack.append([idx, v]) # 건물번호와 높이
    
    # 최종 결과
    for i in range(1, n + 1):
        if cnt[i] > 0:
            print(f'{cnt[i]} {near[i][0]}') # 해당 건물에서 볼 수 있는 건물 수, 가장 가까운 건물 번호 중 건물 번호가 작은 건물의 번호
        else:
            print(0)