[leetcode][42] Trapping Rain Water 문제풀기!
👓 문제 요약
내가 말이야.. 특이한 목욕탕을 만들고 싶거든.. 근데 물이 얼마나 필요할지 잘 모르겠어.. 니가 좀 구해줄래?
자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
대표적으로 이런 문제는 대부분 2 pointer 문제더라!!
일단 물 높이를 생각해보자. 인풋이 [2 ,0 ,0 ,3] 이렇게 주어지면, 왼쪽 기둥은 높이가 2, 오른쪽 기둥은 3 이다. 따라서 물을 다 채우면 왼쪽이 오른쪽 보다 낮기 때문에 높이 2까지만 채워진다.
이 원리를 이용해 왼쪽에서 오른쪽 방향으로 하나씩 참고하는 포인터와 반대로 오른쪽에서 왼쪽 방향으로 참고하는 포인터를 생성한다.
만약 왼쪽에서 하나씩 보다가 현재 기둥이 오른쪽에서 참조하는 기둥의 높이보다 낮거나 같으면 한 칸 물을 채워주고, 반대로 오른쪽 기둥이 더 낮으면 오른쪽에서 물을 채워주는 형식으로 진행한다. 채워주는 양은 현재 물의 높이 - 현재 기둥의 높이라고 생각하면 되겠다. 물을 낮은 곳 부터 차근차근 채워나간다고 생각하자.
왼쪽에서 먼저가던 오른쪽으로 가던 어느쪽으로 기준을 잡던 상관이 없지만 저는 왼쪽으로 기준 삼았습니다!.
그래서 제가 어떻게 풀었냐면 !!
물을 채울 때 높이가 가장 중요하다. 물의 높이는 왼쪽 기둥과 오른쪽 기둥의 높이를 비교하여 낮은 값과, 이때까지 물의 높이 중 더 큰 값을 선택한다. 알아보기 쉽게 다음과 같이 표기하겠다.
Math.max(fixH, Math.min(height[left], height[right]));
// fixH가 물의 높이다.그런 다음 왼쪽 오른쪽 어디를 채울지 선택해 채우면 된다!!.
🥽 소스코드 및 소스해석
var trap = function (height) {
let answer = 0;
let left = 0;
let right = height.length - 1;
let fixH = 0;
while (left < right) {
fixH = Math.max(fixH, Math.min(height[left], height[right]));
if (height[left] <= fixH) {
answer += fixH - height[left];
left++;
} else {
answer += fixH - height[right];
right--;
}
}
return answer;
};🔨 문제 후기
재미있다.
처음에 나는 상당히 긴 코드를 작성했다. 내가 워낙 설계하지 않고 풀다보니 깔끔하게 풀지를 못해서 중간에 값을 변경하고 변경하고 하다가 문제를 통과했다.
다른 사람들이 푼 아주 깔끔한 소스를 보고 약간의 자괴감과 한가지 깨닳음을 얻었따.
코드가 간결해 질수록 버그도 적어진다!!
앞으로 간결하게 코드를 작성하도록 해야할 듯 하다.
Series
Algorithms
이 글은 "Algorithms" 시리즈의 24번째 기록입니다.
- 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
- 02[프로그래머스][2019 kakao] 블록게임 해설
- 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
- 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
- 05[프로그래머스][2019 kakao] 후보키 문제 해설
- 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
- 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
- 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
- 09[백준🔉][16234] 인구이동 문제 해설
- 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
- 11[프로그래머스✈][2020 kakao] 동굴 탐험
- 12[백준🔉][14501] 퇴사 문제 해설
- 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
- 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
- 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
- 16[leetcode][15] 3sum 문제풀기!
- 17[leetcode][16] 3sum closet 문제풀기!
- 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
- 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
- 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
- 21[leetcode][31] Next Permutation 문제풀기!
- 22[leetcode][32] Longest Valid Parentheses 문제풀기
- 23[leetcode][40] Combination Sum II 문제풀기!
- 24[leetcode][42] Trapping Rain Water 문제풀기!
- 25[leetcode][43] Multiply Strings 문제풀기!
- 26[leetcode][44] Wildcard Matching 문제풀기!
- 27[leetcode][45] Jump Game II 문제풀기!