[백준 - Python] 22866 - 탑 보기

0.  문제 링크

 

 

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

22866번: 탑 보기

---

1.  풀이 방법

 

 

문제를 보고 살짝 투포인터로 풀까 고민했는데, 그렇게 풀면 무조건 시간 초과가 날 것 같아서 포기했다.

양쪽을 한 번에 봐야 하나 싶었는데, 생각을 좀 해보니까 양쪽을 한 번에 볼 필요가 없었음

그냥 왼쪽을 봤을 때의 개수를 세고, 오른쪽을 봤을 때의 개수를 세면 되는 일 !

 

그러면 이제 특정한 방향을 봤을 때의 개수와 그때의 건물 번호는 어떻게 세야 할까?

처음은 두 개의 추가 리스트와 while문을 사용해서 풀려고 했다. 근데 이 방법은 매우 좋지 않은 방법임을 금세 깨달았다.

그래서 어떻게 할까 고민 중에 알고리즘 분류에 스택이 있는 걸 봤다.

생각해 보니까 스택에 숫자가 항상 내림차순으로 될 수 있게 정렬하면 된다.

7 1 6이 되면, 1을 pop 하고 6을 넣는다.

그리고 그때 스택에서 내 아래에 있는 숫자가 가장 가까우면서 나보다 큰 건물이 되고, 그때의 스택의 길이가 나보다 큰 애의 개수가 된다.

뭐 아무튼 그렇다.

그렇게 왼쪽, 오른쪽을 보고 이때 가까우면서 큰 건물, 혹은 둘 다 거리가 같다면 왼쪽에 있는 건물의 번호를 연산해서 넣으면 된다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline
print = sys.stdout.write


def sol(flag):
    stack = [(100001, 0)]       # 언더플로우 방지
    if flag:
        lst.reverse()       # 오른쪽에서 왼쪽으로 보기 위해, 이렇게 된다면 내 오른쪽만 바라봄
    for i in lst:
        while maps[i] >= stack[-1][0]:      # 나보다 작은 애들은 일단 팝함
            stack.pop()
        else:
            count[i] += len(stack) - 1      # 길이 -1을 넣어야 함

            match flag:
                case True:
                    what_right = stack[-1][1]       # 내 오른쪽에 나보다 큰 애의 인덱스
                    if count[i]:
                        if what[i] and what_right:
                            left = abs(i + 1 - what[i])     # 왼쪽까지 거리
                            right = abs(what_right - i - 1)     # 오른쪽까지 거리
                            if left > right:        # 왼쪽과 거리가 더 크다면, 오른쪽을 넣는게 맞음
                                what[i] = what_right
                        elif what_right:        # 왼쪽에서 나보다 큰 애의 인덱스가 0이라면, 오른쪽을 넣는게 맞음
                            what[i] = what_right
                case False:
                    what[i] = stack[-1][1]      # 내 왼쪽에 나보다 큰 애의 인덱스
            stack.append((maps[i], i + 1))      # 그리고 스택에 넣음


if __name__ == "__main__":
    n = int(input())
    maps = list(map(int, input().split()))
    lst = [*range(n)]

    count = [0] * n
    what = [0] * n

    sol(False)
    sol(True)

    for i in range(n):
        print("%d " % count[i])
        if count[i]:
            print("%d" % what[i])
        print("\n")

---

3.  마무리

 

 

 

현시점 기준 1등이라 기분이 좋다.

참고로 시간 더 줄이려고 그냥 print문도 sys.stdout.write로 변경했다.

여러분은 굳이 이러진 마십시오,,,,