
๐ค ๋ฌธ์
Trapping Rain Water - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
๐ ํ์ด
ํด๋น ๋ฌธ์ ๋ ๋ฒฝ ๋์ด ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์๋ ๋ฐฐ์ด์ ์ด์ฉํ์ฌ ๋น๊ฐ ์จ ๋ค ๋ฒฝ ์ฌ์ด์ ๊ณ ์ธ ๋น๋ฌผ ์์ ๊ณ์ฐํ๋ ๋ฌธ์ ์ ๋๋ค.
๊ฐ ์์น๋ง๋ค ๊ณ ์ผ ๋น๋ฌผ์ ์์ ๊ณ์ฐํ๋ ๊ณผ์ ์ ํตํด ๋ฌธ์ ํ์ด๋ฅผ ์งํํ๋๋ฐ ์ด ๋ ๊ณ ๋ คํด์ผ ํ ๊ฒ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
# ํ์ฌ ์์น ๊ธฐ์ค์ผ๋ก..
- ์ข์ธก์ ์๋ ๋ฒฝ๋ค ์ค ์ต๋ ๋์ด
- ์ฐ์ธก์ ์๋ ๋ฒฝ๋ค ์ค ์ต๋ ๋์ด
์ ๋ ๊ฐ์ง๋ฅผ ์๋ค๋ฉด ๋ ๊ฐ์ง ์ค ์ต์ ๊ฐ์์ ํ์ฌ ๋์ด๋ฅผ ๋บ ์์ด ๊ณ ์ด๋ ๋น๋ฌผ ์์ด ๋ฉ๋๋ค.
์ฆ, ํ์ฌ ์์น ๋์ด๊ฐ 2์ด๊ณ ์ข์ธก์ด 4, ์ฐ์ธก์ด 5๋ผ๋ ๋์ด๋ฅผ ๊ฐ์ง๊ณ ์๋ค๋ฉด ํ์ฌ ์์น์๋ (4 - 2) ๋งํผ์ ๋น๋ฌผ์ด ๊ณ ์ด๊ธฐ ๋๋ฌธ์ด์ฃ .
์ด๋ ์ฃผ์ํ ์ ์ ํ์ฌ ๋์ด๊ฐ ์ข์ธก ํน์ ์ฐ์ธก๋ณด๋ค ๋๋ค๋ฉด ๋น๋ฌผ์ด ๊ณ ์ด์ง ์์ต๋๋ค.
์์ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์์ฑํ๋ค๊ฐ ์ข ๋ ํจ์จ์ ์ธ ๋ฐฉ๋ฒ์ ์ฐพ๊ฒ๋์๋๋ฐ ๋ชจ๋ ๋ฒฝ ์ค ๊ฐ์ฅ ๋์ ๋ฒฝ ํ๋๋ฅผ ๊ธฐ์ค์ผ๋ก ์ก๋ ํ์ด ๋ฐฉ์์ ์๊ฐํ์ต๋๋ค.
๊ฐ์ฅ ๋์ ๋ฒฝ์ ๊ธฐ์ค์ผ๋ก ์ข์ธก์ ํ์ด๋ณด๊ณ ๊ทธ ๋ค ์ฐ์ธก๋ ํ์ด๋ณด๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ค๋ฉด ํ์ฌ ์์น ๊ธฐ์ค์ผ๋ก ๋งค๋ฒ ์ข, ์ฐ์ธก์ ๋ฒฝ ์ต๋ ๋์ด๋ฅผ ๊ตฌํ์ง ์์๋ ๋๊ธฐ ๋๋ฌธ์ ์กฐ๊ธ ๋ ๋น ๋ฅด๊ฒ ๊ณ์ฐํ ์ ์์ต๋๋ค.
์๋ ์ฝ๋๋ ์ ์ฒด ํ์ด ์ฝ๋์ ์ผ๋ถ๋ถ์ ๋๋ค.
max_height = max(height)
max_place = height.index(max_height)
left_max = height[0]
# left ๋๊ธฐ
for i in range(max_place):
left_max = max(left_max, height[i])
answer += left_max - height[i]
์ฝ๋๋ฅผ ์ดํด๋ณด๊ฒ ๋๋ฉด ๊ฐ์ฅ ๋์ ๋ฒฝ์ ๊ธฐ์ค์ผ๋ก ์ข์ธก์ ํ์ด๋ณด๋ ๊ณผ์ ์ธ๋ฐ ์ข์ธก ๋ฒฝ์ ์ต๋ ๋์ด๋ฅผ ํ์ฌ ์์น๋ฅผ ์ดํด๊ฐ๋ฉฐ ๊ฐฑ์ ํด๋๊ฐ๋ ๊ณผ์ ๋ ํ์ธํ ์ ์์ต๋๋ค. for๋ฌธ ์์ left_max์์ ๊ฐฑ์ ํ๊ณ ์์ฃ !
๋ํ left_max - height[i], ์ฆ ์ข์ธก ๋ฒฝ์ ์ต๋ ๋์ด์ ํ์ฌ ๋์ด์ ์ฐจ๋ฅผ ํตํด ํ์ฌ ์์น์ ๊ณ ์ธ ๋น๋ฌผ ์์ ๊ตฌํ๊ณ ์์ต๋๋ค. ์ด ๊ณผ์ ์ ํตํด for๋ฌธ์ด ๋๋๋ค๋ฉด ๊ฐ์ฅ ๋์ ๋ฒฝ์ ๊ธฐ์ค ์ข์ธก์ ๊ณ ์ธ ๋น๋ฌผ ์์ด ์ ๋ถ ๊ตฌํด์ง๋๋ค.
์ด์ ๋๊ฐ์ ๋ฐฉ์์ผ๋ก ์ฐ์ธก์ ์ดํด๋ณธ๋ค๋ฉด ๋ต์ ๊ตฌํ ์ ์์ต๋๋ค.
๐ป ํ์ด ์ฝ๋๋ ์๋์ ๊ฐ์ต๋๋ค.
class Solution:
def trap(self, height: List[int]) -> int:
answer = 0
max_height = max(height)
max_place = height.index(max_height)
left_max = height[0]
right_max = height[-1]
# left ๋๊ธฐ
for i in range(max_place):
left_max = max(left_max, height[i])
answer += left_max - height[i]
# right ๋๊ธฐ
for i in reversed(range(max_place, len(height))):
right_max = max(right_max, height[i])
answer += right_max - height[i]
return answer
'Algorithm > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] 33. Search in Rotated Sorted Array - Python (0) | 2022.05.05 |
---|---|
[LeetCode] 49. Group Anagrams - Python (3) | 2022.04.26 |