[programmers] ๋ ๋ฐ๋จน๊ธฐ - Java
๋
๋ฐ๋จน๊ธฐ ๊ฒ์์์ ์ฃผ์ด์ง 2์ฐจ์ ๋ฐฐ์ด์ ์ ์๋ฅผ ๊ธฐ๋ฐ์ผ๋ก, ๊ฐ ํ์์ ๊ฐ์ ์ด์ ์ฐ์์ผ๋ก ๋ฐ์ง ์๊ณ ์ป์ ์ ์๋ ์ต๋ ์ ์๋ฅผ ๊ณ์ฐํ๋ Java ์๋ฃจ์
์ ์ ์ํฉ๋๋ค. ๋์ ๊ณํ๋ฒ์ ์ฌ์ฉํ์ฌ ์ด์ ํ์ ์ต๋ ์ ์๋ฅผ ์
๋ฐ์ดํธํ๋ฉฐ, ์ต์ข
์ ์ผ๋ก ์๊ฐ ๋ณต์ก๋๋ O(N)์
๋๋ค.
Sep 23, 2024
๋ ๋ฐ๋จน๊ธฐ
๋ฌธ์ ์ค๋ช
๋
๋ฐ๋จน๊ธฐ ๊ฒ์์ ํ๋ ค๊ณ ํฉ๋๋ค. ๋
๋ฐ๋จน๊ธฐ ๊ฒ์์ ๋
(land)์ ์ด Nํ 4์ด๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ๋ชจ๋ ์นธ์๋ ์ ์๊ฐ ์ฐ์ฌ ์์ต๋๋ค. 1ํ๋ถํฐ ๋
์ ๋ฐ์ผ๋ฉฐ ํ ํ์ฉ ๋ด๋ ค์ฌ ๋, ๊ฐ ํ์ 4์นธ ์ค ํ ์นธ๋ง ๋ฐ์ผ๋ฉด์ ๋ด๋ ค์์ผ ํฉ๋๋ค. ๋จ, ๋
๋ฐ๋จน๊ธฐ ๊ฒ์์๋ ํ ํ์ฉ ๋ด๋ ค์ฌ ๋, ๊ฐ์ ์ด์ ์ฐ์ํด์ ๋ฐ์ ์ ์๋ ํน์ ๊ท์น์ด ์์ต๋๋ค.
์๋ฅผ ๋ค๋ฉด,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
๋ก ๋
์ด ์ฃผ์ด์ก๋ค๋ฉด, 1ํ์์ ๋ค๋ฒ์งธ ์นธ (5)๋ฅผ ๋ฐ์์ผ๋ฉด, 2ํ์ ๋ค๋ฒ์งธ ์นธ (8)์ ๋ฐ์ ์ ์์ต๋๋ค.
๋ง์ง๋ง ํ๊น์ง ๋ชจ๋ ๋ด๋ ค์์ ๋, ์ป์ ์ ์๋ ์ ์์ ์ต๋๊ฐ์ returnํ๋ solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์. ์ ์์ ๊ฒฝ์ฐ, 1ํ์ ๋ค๋ฒ์งธ ์นธ (5), 2ํ์ ์ธ๋ฒ์งธ ์นธ (7), 3ํ์ ์ฒซ๋ฒ์งธ ์นธ (4) ๋
์ ๋ฐ์ 16์ ์ด ์ต๊ณ ์ ์ด ๋๋ฏ๋ก 16์ return ํ๋ฉด ๋ฉ๋๋ค.
์ ํ์ฌํญ
- ํ์ ๊ฐ์ N : 100,000 ์ดํ์ ์์ฐ์
- ์ด์ ๊ฐ์๋ 4๊ฐ์ด๊ณ , ๋ (land)์ 2์ฐจ์ ๋ฐฐ์ด๋ก ์ฃผ์ด์ง๋๋ค.
- ์ ์ : 100 ์ดํ์ ์์ฐ์
์ ์ถ๋ ฅ ์
land | answer |
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] | 16 |
solution.java
class Solution { int solution(int[][] land) { int rows = land.length; // ๋ ๋ฒ์งธ ํ๋ถํฐ ๋ง์ง๋ง ํ๊น์ง ๋ฐ๋ณต for (int i = 1; i < rows; i++) { // ํ์ฌ ํ์ ๊ฐ ์ ์ ๋ํด ์ด์ ํ์ ์ต๋ ์ ์๋ฅผ ์ถ๊ฐํ์ฌ ๊ฐ์ ์ ๋ฐ์ดํธํจ // ํ์ง๋ง ๋์ผํ ์ด์ ์ ์๋ ์ถ๊ฐํ์ง ์๋๋ค land[i][0] += Math.max(land[i - 1][1], Math.max(land[i - 1][2], land[i - 1][3])); land[i][1] += Math.max(land[i - 1][0], Math.max(land[i - 1][2], land[i - 1][3])); land[i][2] += Math.max(land[i - 1][0], Math.max(land[i - 1][1], land[i - 1][3])); land[i][3] += Math.max(land[i - 1][0], Math.max(land[i - 1][1], land[i - 1][2])); } // ์ ๋ต์ ๋ง์ง๋ง ํ์ ์ต๋๊ฐ return Math.max( land[rows - 1][0], Math.max(land[rows - 1][1], Math.max(land[rows - 1][2], land[rows - 1][3])) ); } }
ํต์ฌ ํค์๋
- ๋์ ๊ณํ๋ฒ์ ์ด์ฉํด์ ์ด์ ํ์์ ๊ฐ๋ฅํ ์ต๋ ์ ์๋ฅผ ์ถ๊ฐํ์ฌ land ๋ฐฐ์ด์ ๊ฐ ์ ์ ์ ๋ฐ์ดํธํ๋ค. ๋ฐ๋ผ์ ๋์ผํ ์ด์ ์ฐ์์ ์ผ๋ก ๋ฐ์ง ์๋๋ก ํ ์ ์๋ค.
๊ฒฐ๋ก !
์ด ๊ฒฝ์ฐ ํ์ ๋ฐ๋ณตํ๊ณ ๊ฐ ํ์ ๋ํด ์ผ์ ํ ์๊ฐ์ ๊ฐ์ด ์
๋ฐ์ดํธ๋๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๋
O(N)
์ด ๋๋ค. Share article