[python] 백준 14719 - 빗물

출처 : 백준, https://www.acmicpc.net/problem/14719

14719번: 빗물

 

다른 사람들 풀이 보니까 다 비슷하던데

나만 이렇게 생각했나봐.............

 

 

풀이

 

def solution(world):
  sum = 0

  for line in world:
    count = 0
    ing = False
    for box in line:
      if not ing and box == 1:#counting 시작
        ing = True
      elif ing and box == 1:#counting 중 벽 만나면 update
        sum += count
        count = 0
      elif ing and box == 0:#counting 중
        count += 1

  return sum

if __name__ == '__main__':
  n, m = map(int, input().split())
  height = list(map(int, input().split()))
  world = []

  for i in range(n):
    width = []
    for j in range(m):
      if i < height[j]:
        width.append(1)
      else:
        width.append(0)

    world.append(width)

  print(solution(world))

 

로직은 다음과 같다.

 

1. 행 별로 지도를 1(벽)과 0(빈 공간)으로 mapping한다.

2. 각 행을 순회하는데 처음 1(벽)을 만나면 카운팅을 시작한다 (ing = True)

3. 카운팅을 시작한 상태에서 빈 공간(0)을 만나면 count += 1

4. 카운팅을 시작한 상태에서 벽(1)을 만나면 sum += count하고 count = 0으로 초기화

5. 반복

---

 

시간 복잡도

 

O(n)

 

다른 사람의 풀이를 보면서 알게 된 점

 

열로 푸는 풀이

 

if __name__ == '__main__':
  n, m = map(int, input().split())
  height = list(map(int, input().split()))
  water = 0

  for i in range(1,m-1):
    w_h = min(max(height[:i]), max(height[i+1:])) - height[i]
    
    if w_h >= 0:
      water += w_h

  print(water)

 

 

 

예제 1과 같은 세계가 있다고 하자.

 

 

첫 번째 열과 마지막 열에 차는 빗물은 고려할 필요가 없다. (밖으로 벽이 존재하지 않기 때문)
두 번째 열에 쌓이는 빗물을 생각해보자. 빗물은 벽까지만 쌓일 수 있으므로 양쪽의 벽이 모두 존재하는 곳까지만 쌓인다.

즉, 좌/우의 열 중 왼쪽의 가장 높은 벽(3)과 오른쪽의 가장 높은 벽(4) 중 작은 쪽까지 쌓이게 된다.

바닥은 내가 현재 있는 열의 값이므로 min(왼쪽, 오른쪽) - 현재 열 값 = 현재 열에 쌓인 물의 값이라는 식을 세울 수 있다.

 

 

확인하기 위해 세 번째 열에서도 해보자.

min(왼쪽, 오른쪽)은 3이고 바닥은 1이므로 2만큼 쌓이게 된다.이를 합친 값이 총 빗물의 양이다.

 

 

고찰

 

열로 풀 수 있지 않을까 싶었는데 바로 떠오르는 풀이가 행을 이용한 풀이여서 행으로 풀었다.

그런데 나 빼고 다 열로 풀었더라.....하긴 그게 더 깔끔하긴하네....문제 분석을 하고 풀어야할 듯