[백준/파이썬] 22866 탑 보기

#문제링크

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

22866번: 탑 보기

#나의풀이

import sys

if __name__=="__main__":
    N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    near = [[-1, 2147000000] for _ in range(N)]
    count = []
    stack = []
    for i in range(N):
        while len(stack) > 0 and stack[-1][0] <= arr[i]:
            stack.pop()
        count.append(len(stack))
        if len(stack) > 0:
            near[i] = [stack[-1][1], i-stack[-1][1]]
        stack.append([arr[i], i])


    stack = []

    for i in range(N-1, -1, -1):
        while len(stack) > 0 and stack[-1][0] <= arr[i]:
            stack.pop()
        count[i] += len(stack)
        if len(stack) > 0:
            if stack[-1][1] - i < near[i][1]:
                near[i][0] = stack[-1][1]
        stack.append([arr[i], i])

    for i in range(N):
        if count[i] > 0:
            print(count[i], near[i][0]+1)
        else:
            print(0)

#해설

시간초과로 몇번 풀었는지 모르겠다. 시간복잡도 계산하는걸 조금 더 공부해야겠다는 생각이 들었다.

	N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    near = [[-1, 2147000000] for _ in range(N)]
    count = []
    stack = []

입력값을 보면 최대 10만까지 N이 있다 따라서 완전탐색을 하면 무조건 터진다. 근데 완탐으로 한 5번 풀었던거 같다.

입력들을 받고 가장 가까운 수가 무엇인지 확인하기 위해 near라는 2차원 리스트를 만들었다 [i][0]에는 가장 가까운 인덱스가 들어갈 것이고 [i][1]에는 [i][0]의 인덱스와 i에 거리가 얼마나 되는지 나타낼것이다. count 리스트는 각 숫자마다 보이는 빌딩개수를 넣을것이고 stack에는 [i][0]에는 값을 넣을것이고 [i][1]에는 인덱스 즉 위치를 넣어 표시를 한다.

 

    	for i in range(N):
        while len(stack) > 0 and stack[-1][0] <= arr[i]:
            stack.pop()
        count.append(len(stack))
        if len(stack) > 0:
            near[i] = [stack[-1][1], i-stack[-1][1]]
        stack.append([arr[i], i])

각 자리에 왼쪽에 있는 빌딩들을 확인하기 위해 -> 방향으로 이동하는 반복문이다.

while문은 stack안의 값이 들어 있고 stack의 마지막값 즉 왼쪽에 있는 빌딩의 첫번째가 현재 빌딩보다 작다면 계속해서 빌딩들을 제거해준다. 이후 왼쪽에 있는 빌딩들이 현재 빌딩보다 작은 애들이 없어졌다면 왼쪽에 보이는 빌딩들의 개수를 세어주기 위해 count에 append로 현재 스택의 길이 즉 왼쪽 빌딩의 개수를 세어준다. 이후 스택에 값이 들어가 있다면 보이는 빌딩이 있다는것을 의미하므로 가장 가까운 마지막값 stack[-1][1]인 위치값과 i-stack[-1][1]인 현재위치-가장가까이보이는 왼쪽빌딩위치의 값을 넣어준다. 이후 왼쪽 빌딩중에 현재 빌딩보다 작은 빌딩은 없으므로 stack에 빌딩의 값과 위치를 넣어준다.

 

	stack = []

    for i in range(N-1, -1, -1):
        while len(stack) > 0 and stack[-1][0] <= arr[i]:
            stack.pop()
        count[i] += len(stack)
        if len(stack) > 0:
            if stack[-1][1] - i < near[i][1]:
                near[i][0] = stack[-1][1]
        stack.append([arr[i], i])

스택을 초기화 하고 이번에는 <- 방향으로 진행하며 오른쪽 빌딩의 개수를 세어줄것이다.

스택에 빌딩을 없애는 부분과 개수를 세어주는 부분은 왼쪽으로 셀 때와 같은 방법으로 해주고

오른쪽 빌딩이 있을경우 즉 stack의 길이가 0보다 클 경우에 마지막값 즉 오른쪽에서 가장 가까운 빌딩의 위치와 현재 위치를 뺀 값이 왼쪽에서 가장 가까웠던 빌딩보다 작을때만 변경이 일어나 조건문을 걸어주고 조건이 맞을경우 값을 바꿔준다. 이때 더이상 위치의 차이는 필요하지 않으므로 위치값만 갱신해주고 왼쪽과 같이 stack의 빌딩의 값과 위치를 추가해준다.