[python] 백준 - 14719 빗물
오늘은 백준 사이트의 문제를 함께 풀어보려 한다.
오늘의 문제는 빗물이라는 문제로
주어진 배열을 사용해
고이는 빗물의 총량을 구하는 문제다.
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
우선 바로 코드를 구현하기에 앞서서
나의 실패한 아이디어와 그 요인에 대해 알아보고,
그다음 정답 코드에 대해 이야기해보겠다.
1. 실패한 아이디어
처음에는 기준은 따로 잡지 않고,
벽이 되는 지점들을 높이를 통해 구해
그 안의 존재하는 블록들을 빼는 방법을 생각했다.
사실 아이디어 자체가 명확하지도 않고
또한, 수많은 예외사항이 존재하다 보니
어디서부터 어디까지 고쳐야 할지 감이 잘 오지 않았다.
그래서 다른 분들의 코드를 많이 찾아봤고
그중에서 내 아이디어보다
더 나에게 명확하게 와 닿는 아이디어를 찾을 수 있었다.
2. 성공 아이디어
[python] 백준 - 14719. 빗물
🤔문제 해결 G5 | 구현, 시뮬레이션 며칠 전 nhn 코테 문제랑 비슷한 문제. 그 때는 자바로 풀었기도 하고, 더 복잡하게 푼거같다. 딱히 어려운 기술을 요구하는 문제는 아니다. 오른쪽으로 가면서
deok2kim.tistory.com
바로 이 분의 아이디어였는데,
아이디어와 코드 자체가 명료했다.
내가 이해한 바로 다시 설명하자면
하나하나의 기준점을 정해
왼쪽과 오른쪽의 최댓값을 구하고
그를 통해
기준점에 쌓인 빗물의 값을 확인하는 방법이다.
만약 첫 번째 블록이라면
왼쪽은 존재하지 않으므로 패스하고
오른쪽에서는 가장 큰 값이 4칸 높이의 블록이다.
오른쪽에 높은 블록이 있지만,
왼쪽에는 블록이 없기에
물이 고이지 못한다.
두 번째 블록이라면
왼쪽은 가장 큰 값이 3칸 높이의 블록하고
오른쪽에서는 가장 큰 값이 4칸 높이의 블록이다.
오른쪽에 더 높은 블록이 있지만
양쪽으로 막아줘야 벽이 생길 수 있기 때문에
이러한 경우 더 낮은 3칸 높이까지
빗물이 쌓일 수 있고
두 번째 블록의 높이는 1이었으므로
두 번째 블록 위치에 고이는 빗물을
3-1 = 2 가 된다.
이러한 방식으로 처음부터 끝까지 모든 점을 확인하며
고이는 빗물의 양을 더하면
정답을 구할 수 있다.
3. 코드 구현
def check(s):
global ans
# 답을 담을 전역 변수 ans
left_maxV = rain[s]
right_maxV = rain[s]
# 최대 값을 구하기 위해 왼쪽 최대값과 오른쪽 최대값의 초기값을 자신으로 세팅해놓는다.
for i in range(s):
# 왼쪽으로 돌면서
if left_maxV < rain[i]:
left_maxV = rain[i]
# 최대값을 구한다.
for i in range(s+1, W):
# 오른쪽으로 돌면서
if right_maxV < rain[i]:
right_maxV = rain[i]
# 최대값을 구한다.
if left_maxV > rain[s] and right_maxV > rain[s]:
# 만일 양쪽 최대값이 자신 보다 크다면 빗물이 고일 수 있다는 의미로
# cf) 만일 왼쪽 벽이나 오른쪽 벽이 없는 경우는 자기 자신의 높이를 저장하고 있으므로 if문에서 벗어난다.
ans += min(left_maxV, right_maxV)-rain[s]
# 그 둘 중 작은 값에서 자신을 빼 고이는 양을 구한다.
H, W = map(int, input().split())
rain = list(map(int, input().split()))
마무리
알고리즘을 배울수록
아이디어의 중요성을 뼈저리게 느끼고 있다.
처음에는 아이디어보다는 구현에 어려움을 강하게 느꼈지만,
시간이 지나면서
둘 다에 많은 시간이 소요되고 어려움을 겪고 있기 때문이다.
이럴 때는 특히 다른 분들의 코드를 보고
생각해보는 것이
많은 도움을 주는 것 같다.
요즘 블로그에 뜸했는데,
블로그에 뜸했던 만큼
많이 나태해진 거 같다.
앞으로는 블로그에도 최대한
자주 들리며
열심히 공부해야겠다!
*잘못된 부분이 있다면 댓글 부탁드리겠습니다!