[programmers] ๋•…๋”ฐ๋จน๊ธฐ - Java

๋•…๋”ฐ๋จน๊ธฐ ๊ฒŒ์ž„์—์„œ ์ฃผ์–ด์ง„ 2์ฐจ์› ๋ฐฐ์—ด์˜ ์ ์ˆ˜๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ, ๊ฐ ํ–‰์—์„œ ๊ฐ™์€ ์—ด์„ ์—ฐ์†์œผ๋กœ ๋ฐŸ์ง€ ์•Š๊ณ  ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” Java ์†”๋ฃจ์…˜์„ ์ œ์‹œํ•ฉ๋‹ˆ๋‹ค. ๋™์  ๊ณ„ํš๋ฒ•์„ ์‚ฌ์šฉํ•˜์—ฌ ์ด์ „ ํ–‰์˜ ์ตœ๋Œ€ ์ ์ˆ˜๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๋ฉฐ, ์ตœ์ข…์ ์œผ๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N)์ž…๋‹ˆ๋‹ค.
DriedPollack's avatar
Sep 23, 2024
[programmers] ๋•…๋”ฐ๋จน๊ธฐ - Java

๋•…๋”ฐ๋จน๊ธฐ

๋ฌธ์ œ ์„ค๋ช…

๋•…๋”ฐ๋จน๊ธฐ ๊ฒŒ์ž„์„ ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋•…๋”ฐ๋จน๊ธฐ ๊ฒŒ์ž„์˜ ๋•…(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

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog