[programmers] ํ๊ฒ ๋๋ฒ- Java
'ํ๊ฒ ๋๋ฒ' ๋ฌธ์ ๋ ์ฃผ์ด์ง ์ซ์ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ๋ํ๊ฑฐ๋ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ฐพ๋ ๊ฒ์
๋๋ค. ์ด ๋ฌธ์ ๋ ์ฌ๊ทํจ์๋ฅผ ์ฌ์ฉํ์ฌ ํด๊ฒฐํ๋ฉฐ, ๊ฐ ์ธ๋ฑ์ค์์ ์ซ์๋ฅผ ๋ํ๊ฑฐ๋ ๋บ ๊ฐ์ ์ฌ๊ทํธ์ถ๋ก ์ ๋ฌํฉ๋๋ค. ๋ฐฐ์ด์ ๋์ ๋๋ฌํ๋ฉด, ๋ง๋ค์ด์ง ํฉ๊ณ๊ฐ ํ๊ฒ ๋๋ฒ์ ์ผ์นํ๋์ง ํ์ธํ๊ณ , ๊ทธ๋ ๋ค๋ฉด 1์ ๋ฐํํฉ๋๋ค. ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ํ์ฌ ์ต์ข
์ ์ผ๋ก ๋ฐฉ๋ฒ์ ์๋ฅผ ์ถ๋ ฅํฉ๋๋ค.
Apr 01, 2024
ํ๊ฒ ๋๋ฒ
๋ฌธ์ ์ค๋ช
n๊ฐ์ ์์ด ์๋ ์ ์๋ค์ด ์์ต๋๋ค. ์ด ์ ์๋ค์ ์์๋ฅผ ๋ฐ๊พธ์ง ์๊ณ ์ ์ ํ ๋ํ๊ฑฐ๋ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด [1, 1, 1, 1, 1]๋ก ์ซ์ 3์ ๋ง๋ค๋ ค๋ฉด ๋ค์ ๋ค์ฏ ๋ฐฉ๋ฒ์ ์ธ ์ ์์ต๋๋ค.
1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3
์ฌ์ฉํ ์ ์๋ ์ซ์๊ฐ ๋ด๊ธด ๋ฐฐ์ด numbers, ํ๊ฒ ๋๋ฒ target์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋ ์ซ์๋ฅผ ์ ์ ํ ๋ํ๊ณ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ์ฃผ์ด์ง๋ ์ซ์์ ๊ฐ์๋ 2๊ฐ ์ด์ 20๊ฐ ์ดํ์ ๋๋ค.
- ๊ฐ ์ซ์๋ 1 ์ด์ 50 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- ํ๊ฒ ๋๋ฒ๋ 1 ์ด์ 1000 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
์ ์ถ๋ ฅ ์
numbers | target | return |
[1, 1, 1, 1, 1] | 3 | 5 |
[4, 1, 2, 1] | 4 | 2 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ฌธ์ ์์์ ๊ฐ์ต๋๋ค.
์
์ถ๋ ฅ ์ #2
+4+1-2+1 = 4
+4-1+2-1 = 4
- ์ด 2๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ผ๋ฏ๋ก, 2๋ฅผ return ํฉ๋๋ค.
solution.java
class Solution { public int solution(int[] numbers, int target) { return findWaysHelper(numbers, target, 0, 0); } private int findWaysHelper(int[] numbers, int target, int index, int sum) { if (index == numbers.length) { return sum == target ? 1 : 0; } int waysWithAddition = findWaysHelper(numbers, target, index + 1, sum + numbers[index]); int waysWithSubtraction = findWaysHelper(numbers, target, index + 1, sum - numbers[index]); return waysWithAddition + waysWithSubtraction; } }
ํต์ฌ ํค์๋
- ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํด์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค.
- ์ธ๋ฑ์ค๋ฅผ 1์ฉ ์ฆ๊ฐ์ํค๊ณ , sum์ ๊ฐ์ ๊ทธ ๋ค์ ์ธ๋ฑ์ค์ ๊ฐ์ ๋ํ ๊ฐ์ผ๋ก ํจ์๋ฅผ ์ฌ๊ทํธ์ถํ๊ณ , sum์ ๊ฐ์ ๊ทธ ๋ค์ ์ธ๋ฑ์ค์ ๊ฐ์ ๋บ ๊ฐ์ผ๋ก ํจ์๋ฅผ ์ฌ๊ทํธ์ถํ๋ค.
- ์ธ๋ฑ์ค๊ฐ ์ฃผ์ด์ง ๋ฐฐ์ด์ ๋๊น์ง ๋๋ฌํ ๊ฒฝ์ฐ, ํ๊ฒ ๋๋ฒ๊ฐ ๋ง๋ค์ด์ง๋ค๋ฉด 1์ ๋ฆฌํดํ๋ค.
- ์ฒ์ ํจ์๋ฅผ ํธ์ถํ ๊ณณ์ผ๋ก ๋์์ค๋ฉด ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ํด์ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๊ฒฐ๋ก !
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ ์๊ณ ๋ฆฌ์ฆ์ ์ง๋ ์ฐ์ต์ ํ ์ ์์๋ค.
Share article