[백준-파이썬] 14719: 빗물

문제 보러 가기

접근 🔥

자기보다 높은 블록이 좌우에 있어야 빗물이 고인다!
높이 별로 쭉~ 돌면서, 그 높이보다 낮게 쌓인 지점이 있는지 보았다.
그 지점이 있으면, 그 지점에서 왼쪽과 오른쪽에 그 높이보다 높게 블록이 쌓였는지 보았다.
양쪽에 그 지점보다 높게 블록이 쌓인 지점이 있으면, 그 지점에는 물이 고일 수 있다.

그림에서처럼 1번 동그라미들에서 각각 좌우에 본인보다 높은 지점이 있는지 봐주고, 2번 동그라미 친 부분에서도 그렇게 하고.. 이렇게 다 봐줬다..

최악의 경우를 생각해봤는데, 500(높이) X 500(너비) X 500(좌우 봐주는 것) 정도니까 시간 내에 통과할 것 같아서, 이렇게 코드를 짰다..
좀 비효율적인 것 같긴 하지만 시간 내에 통과는 했다.
다른 분들의 코드도 봐야겠다~

코드 👩‍💻

import sys

input = sys.stdin.readline
MIIS = lambda: map(int, input().split())
H, W = MIIS()
arr = list(MIIS())

ans = 0


def is_poll(depth, width):
    if width == 0 or width == W - 1:
        return False

    flag1 = False
    flag2 = False
    # 좌
    for i in range(width):
        if arr[i] > depth:
            flag1 = True
    # 우
    for i in range(width + 1, W):
        if arr[i] > depth:
            flag2 = True

    if flag1 == True and flag2 == True:
        return True
    else:
        return False


# 맨 아래부터
for depth in range(min(arr), max(arr)):
    for j in range(W):
        # 빈 칸
        if depth >= arr[j]:
            # 좌우에 자기보다 큰 수 있으면 더하기
            if is_poll(depth, j):
                ans += 1

print(ans)

약간의 개선 😁

is_poll에서 좌, 우에 그 지점보다 높은 지점이 있는지 봐줄 때, 그런 지점이 한 군데라도 있으면 되니까 그런 지점을 만난 후에는 break 했다.

import sys

input = sys.stdin.readline
MIIS = lambda: map(int, input().split())
H, W = MIIS()
arr = list(MIIS())

ans = 0


def is_poll(depth, width):
    if width == 0 or width == W - 1:
        return False

    flag1 = False
    flag2 = False
    # 좌
    for i in range(width):
        if arr[i] > depth:
            flag1 = True
            break
    # 우
    for i in range(width + 1, W):
        if arr[i] > depth:
            flag2 = True
            break

    if flag1 == True and flag2 == True:
        return True
    else:
        return False


# 맨 아래부터
for depth in range(min(arr), max(arr)):
    for j in range(W):
        # 빈 칸
        if depth >= arr[j]:
            # 좌우에 자기보다 큰 수 있으면 더하기
            if is_poll(depth, j):
                ans += 1

print(ans)

그랬더니 시간이 많이 단축되었다 ~~ ^0^