[BOJ] 백준 22866번: 탑 보기

1일 1PS 6일차!

문제

---

골드 3

• 3 7 1 6 3 5 1 7 로 정렬된 빌딩이 존재할 때 각 빌딩에서 왼쪽으로 보이는 빌딩을 구하는 방법

  • stack 에 이전까지 내림차순된 빌딩의 높이를 넣고 가장 마지막 요소부터 현재 빌딩의 높이와 계속 비교한다.
  • stack 의 변화는 다음과 같다.
    • index 0 : [] -> [3] (빈 stack 이기에 현재 빌딩의 높이를 추가한다.)
    • index 1 : [3] -> [] -> [7] (stack 에 자신보다 높은 빌딩이 없기에 pop 하다가 빈 stack 이기에 자신의 높이 추가)
    • index 2 : [7] -> [7, 1] (stack 의 마지막 요소가 자신보다 높기에 해당 stack 이 자신이 볼 수 있는 왼쪽 빌딩의 높이들이며 마지막에 자신의 높이를 추가)
    • index 3 : [7, 1] -> [7] -> [7, 6] (stack 의 마지막 요소가 자신보다 낮기에 pop 하고 다음을 비교, 마지막에 자신의 높이 추가)
    • index 4 : [7, 6] -> [7, 6, 3]
    • …

• 위 과정을 통해 각 빌딩에서 왼쪽으로 볼 수 있는 빌딩들이 정렬된다. 반대쪽으로 오른쪽으로 볼 수 있는 빌딩도 동일한 과정을 통해 정리한다.

포인트

---

1. 정방향으로 왼쪽으로 볼 수 있는 빌딩들을 정렬한다.

   • 이때 높이가 아닌 index 를 저장하였다.
   • 추가로 원하는 출력을 위해서는 굳이 모든 요소들을 저장할 필요가 없었다.
   • cnt와 가장 가까운 index 를 출력해야하는데, 정렬하는 과정에서 stack 의 요소 개수와 stack 의 마지막 요소가 현재 가장 가까운 index 이기에 이를 [cnt, index] 로 배열에 추가하였다.
2. 역방향으로 오른쪽에서 볼 수 있는 빌딩들을 정렬한다.
3. sight 배열에는 [왼쪽에서 볼 수 있는 빌딩의 수, 왼쪽으로 볼 수 있는 빌딩 중 가장 가까운 index, 오른쪽으로 볼 수 있는 빌딩의 수, 오른쪽으로 볼 수 있는 빌딩 중 가장 가까운 index] 가 저장된다.
4. sight 배열에서 왼쪽, 오른쪽 빌딩 유무와 왼쪽과 오른쪽에서 가장 가까운 거리를 판단해 출력한다.

코드

---

n = int(input())

buildings = list(map(int, input().split()))

sight = [[] for _ in range(n)]

stack = []

for i in range(n):
    while stack:
        index = stack[-1]
        if buildings[index] > buildings[i]:
            sight[i] += [len(stack), stack[-1]]
            stack.append(i)
            break
        stack.pop()
    if not stack:
        stack.append(i)

stack = []

for i in range(n - 1, -1, -1):
    while stack:
        index = stack[-1]
        if buildings[index] > buildings[i]:
            sight[i] += [len(stack), stack[-1]]
            stack.append(i)
            break
        stack.pop()
    if not stack:
        stack.append(i)

for i in range(n):
    if sight[i]:
        if len(sight[i]) == 2:
            print(str(sight[i][0]) + " " + str(sight[i][1] + 1))
        else:
            if i - sight[i][1] <= sight[i][3] - i:
                print(str(sight[i][0] + sight[i][2]) + " " + str(sight[i][1] + 1))
            else:
                print(str(sight[i][0] + sight[i][2]) + " " + str(sight[i][3] + 1))
    else:
        print("0")