[BOJ] #14719. 빗물(Python)

mingguriguri·2022년 12월 10일

python 백준 시뮬레이션 알고리즘

Python으로 공부하는 Algorithm

목록 보기

9/10

#14719. 빗물

유형: 시뮬레이션
작성일시: 2022년 12월 9일 오전 11:47

📖문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력1 /출력 1

예제1
입력
4 4
3 0 1 4
출력
5

예제2
입력
4 8
3 1 2 3 4 1 1 2
출력
5

예제3
입력
3 5
0 0 0 2 0
출력
0

🧐분석

👀유형 파악

이러한 문제 유형을 ‘구현’문제라고 한다.

📢 ‘구현(Implementation)’이란, 머리 속에 있는 알고리즘을 소스코드로 바꾸는 과정’을 의미한다.

구현문제

풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제
- 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다
- ex) 완전탐색, 시뮬레이션 유형
  - 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법
  - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제

구현하기 어려운 문제란?

알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
특정 소수점 자리까지 출력해야 하는 문제
문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 파싱해야 하는 문제

⇒ 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다.

구현 문제를 풀기 위한 선행 조건

프로그래밍 문법의 정확한 숙지
라이브러리 사용경험

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시하여 문제의 길이가 꽤 긴 편이다.
- 하지만, 고차원적 사료적을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하면 오히려 쉽게 풀 수 있다.
C/C++/Java에서 구현 유형 문제가 더 어렵게 다가온다.
- 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데 C/C++/JAVA에서는 문자열 처리가 파이썬에 비하여 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용하기 때문이다.
- 자신만의 코드 노트를 잘 활용하여 이를 보완할 수 있다.

출처 : [Algorithm] 구현 문제란?

🔍문제 분석!

물이 고이는 조건을 찾자

양 옆이 모두 벽이 있어야 한다.
어느 한 구간이 아니라 현재 위치에서 왼쪽, 오른쪽을 다 봐야 한다!

모듈화를 해보자

정답

# 입력
height, weight = map(int, input().split())
ground = list(map(int, input().split()))
rain = 0
# for문을 통해서 양 옆 비교하기

for i in range(1, weight-1):
    left = max(ground[:i])
    right = max(ground[i+1:])
    std = min(left, right)

    if ground[i] < std:
        rain += std - ground[i]

# 값 출력
print(rain)

🎯풀이과정

최종 답안은 맨 아래에 있습니다.

1번째 시도


#세로 : height 가로 :weight
# 입력받기
weight, height = map(int, input().split())
ground = list(map(int, input().split()))
#양옆 비교
	left = max(ground [:i])
	right = max(ground [i+1:])

	if ground[i] < left:
		rain+= left - ground [i]
if ground[i] < right:
		rain+= right - ground [i]
#값 출력
print(rain)

🚨이 코드의 문제점 : 이중으로 더해진다!

3번째 시도

#세로 : height 가로 :weight
# 입력받기
weight, height = map(int, input().split())
ground = list(map(int, input().split()))
rain = 0
for i in range (1, weight) :
#양옆 비교
	left = max(ground [:i])
	right = max(ground [i+1:])
	std = min(left, right)

	if ground[i] < std:
		rain+= std- ground [i]

NameError: name 'rain' is not defined
ValueError: max() arg is an empty sequence

Name error → rain을 0으로 초기화해줌
Value error → 수치를 비교할 수 있는 데이터가 존재하지 않는 빈 리스트를 제공할 때 발생하는 에러이다. 리스트가 빈 리스트인지 확인하거나 len() 명령어를 통해 리스트 요소의 개수를 확인한 다음 작업을 수행하게 하면

코드가 아무 문제없이 정상 작동하는 것을 확인할 수 있다.

⇒ 해결 : for문의 범위 설정이 잘못 되었음!
왜냐하면, 맨 왼쪽과 맨 오른쪽은 물이 고일 수 없기 때문에 그 부분은 제외하고 탐색해야 함

따라서 for i in range(1, weight-1)로 변경!

3번째 시도 : for문의 범위 수정

weight, height = map(int, input().split())
ground = list(map(int, input().split()))
rain = 0
# for문을 통해서 양 옆 비교하기
 
for i in range(1, weight-1):
    left = max(ground[:i])
    right = max(ground[i+1:])
    std = min(left, right)
 
    if ground[i] < std:
        rain += std - ground[i]
 
# 값 출력
print(rain)

🚨값이 제대로 안 나오고, 백준에서도 틀렸다고 나옴

⇒ 왜지?!

⇒ for범위에서 weight-1은 맞다.근데 입력 받을 때 weight, height 순으로 받았기 때문에 4, 8 에서 4가 들어가기 때문이다

최종 : 입력값 위치 수정

# 입력
height, weight = map(int, input().split())
ground = list(map(int, input().split()))
rain = 0
# for문을 통해서 양 옆 비교하기

for i in range(1, weight-1):
    left = max(ground[:i])
    right = max(ground[i+1:])
    std = min(left, right)>

    if ground[i] < std:
        rain += std - ground[i]

# 값 출력
print(rain)

결과

🤔회고

매번 ‘이걸 어떻게 코드로 구현하지?’ 하고 얘기하는데, 시뮬레이션 문제가 있다는 것을 오늘을 계기로 알게 되었다.
- 실제로 삼성, 카카오 등에서 코딩테스트 문제로 시뮬레이션 문제를 많이 낸다고 한다!
- 시뮬레이션 문제란, 풀이를 떠올리는 건 쉽지만, 구현하는 것은 어려운 문제를 말한다!! 이번에 이렇게 배워간다~~
빗물 문제도 그냥 보기에는 어떻게 풀어야 할지 알겠는데 코드로 구현하자니 조건을 어떻게 설정해야 할지 막막했다.
이럴 때는 역시나 다른 문제들을 푸는 것처럼 하나하나 식으로 풀거나 그림을 그린 후 규칙성이나 점화식을 만들어낸 뒤!
컴퓨터의 입장에서 조건이 무엇일지 생각해보는 방식으로 하면 좋을 것 같다!
매번 스터디에서 다들 2시간~3시간 사이의 시간이 걸렸는데 오늘은 딱 1시간만에 끝났다! 그간 다들 실력이 는 것 같다!