[백준] 옥상 정원 꾸미기 6198번 Python

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO November 2006 Contest > Silver 1번

• 잘못된 번역을 찾은 사람: jh05013
• 문제를 번역한 사람: skynet
• 문제의 오타를 찾은 사람: twinparadox, vl0612

! 문제 생각&풀이 !

자료구조 문제에 항상 조금 약했다 생각할 부분이 많아지면 많아질수록 내 생각 정리가 한번씩 꼬였기 때문에 코드를 작성하다가 내가 무엇을 하려고 이 코드를 만들고있는건지 꼬일때가 많았다.

처음엔 이중포문으로 풀어보았다 작성하면서 '어 이거 시간초과날거같은데?' 생각은했지만 일단 정답은 출력이 되었기에 제출을 해보았다. 역시나 시간초과였다. 그래서 방식을 조금 수정했다.

 

스택 리스트를 생성해서 스택이 빌 때까지 그리고 스택의 맨 오른쪽 요소가 탐색중인 해당 빌딩의 요소보다 작을때까지 연산을 수행했다. 맨 오른쪽 요소가 빌딩을 탐색중인 해당 원소보다 작다면 맨 오른쪽 요소를 pop을 해서 스택에서 제거한다.

그게 아니라 반대의 경우라면 그 남은 스택의 길이만큼 cnt에 덧셈을 해주어 cnt를 출력하였다. 스택이 빌때까지 반복을 돌리고 계속 append 해주는 형식이다. 결과는 똑같이 시간이 3000ms 정도로 오래걸리긴했지만 아슬아슬하게 통과

! 첫 Code ! (시간초과)

# 옥상 정원 꾸미기 G5

# N
N = int(input())
arr = []
for i in range(N):
    building = int(input())
    arr.append([i, building])
# print(arr)

cnt = 0
print(arr)
for i in range(N-1):
    for j in range(i+1, N):
        if arr[i][1] > arr[j][1]:
            # print(arr[i][1], arr[j][1])
            cnt += 1
        elif arr[i][0] < arr[j][0]:
            # print(arr[i][0], arr[j][1])
            break
print(cnt)

! 수정 Code ! (통과)

# 옥상 정원 꾸미기 G5

# N
N = int(input())
arr = []
for _ in range(N):
    building = int(input())
    arr.append(building)
# print(arr)

cnt = 0
stack = []
for i in range(N):
    while stack:
        if arr[i] >= stack[-1]:
            # print(f'arr[i] :', arr[i])
            # print(f'스택 리스트 :',stack)
            stack.pop()
        else:
            # print(stack)
            # print(len(stack))
            cnt += len(stack)
            break

    stack.append(arr[i])
print(cnt)