Python Trapping Rain Water 풀이 + 해석

안녕하세요 코딩 문제로는 오랜만에 글을 올리는것 같네요 처음인가?

이 문제는 아마존, 구글, 애플 혹은 컴공 대학 전공자 들에 졸업 문제로 많이 출제되는 유형에 문제라고 하더라고요! 저는 아직 초짜긴한데 불가피한 이유로 이 문제를 풀게 되었습니다. 저는 이 문제를 반은 풀었긴했는데 마지막 코드 작성하는걸 못해서 그냥 영어 해설보고 마무리 지었습니다.

leetcode.com

그냥 간단하게 문제를 설명하자면 저 블럭들은 1X1 크기이고 파란색 블럭은 물을 의미합니다. 저 map 블럭에는 얼마만큼에 물이 담기는지를 찾는 문제입니다.

• 양 옆에 기둥이 있어야 물이 찬다.
• 양 옆에 기둥에 min 만큼 물이 찰 수 있다.

array에 있는 숫자들을 반복하면서 현 index 양 옆에 있는 각 두 기둥에 길이를 찾은 다음 그 기둥 둘이 min를 찾고 현 index에 수는 빼주면 그 자리에 물이 얼마나 찰 수 있는지에 대한 값이 나오게 되는데 이것들을 다 더해주면 완성된다.

예)

0,1,0,3

반복문을 통해 현 index가 1이면 1의 양옆에는 기둥이 없으니 아무 결과도 안나오니 넘어가고 index 2면 0인데

양 옆에는 기둥이 있다 max로 길이를 찾아보니 1과 2가 나왔고 이 둘 기둥에  min인 1 블럭만큼 물이 찰 수 있다. 여기서 1에 현 index 값인 0을 빼주면 총 1 블럭에 물이 찰 수 있다는 결과가 나온다.

코드 :

더 다양한 코드가 있지만 이게 젤 간단한 코드인것같다 ( 입맛대로 변경함 ) 위 설명만 이해하면 웬만큼 코딩을 할 줄 아는 사람들은 알고리즘을 쉽게 짰을지도 모르겠다 하지만 난 왕초짜

알고리즘 설명하는게 좀 어려워 횡설수설 해 보일지도 모르지만 나름 최선을 다했다. 코드는 짧고 간결하게 답만나오면 된다.

이상 왕초짜에서 벗어나고 싶은 공부 안 하는 학생이였습니다.