📍 타겟 넘버
💡 문제
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 이하인 자연수입니다.
✅ 풀이
👆 첫 번째 풀이(성공)
성?공?이다. 나는 오늘도 이해를 못했다. 이번에도 탐색 알고리즘을 사용해서 풀어야하는 문제였다. 탐색? 그게 뭐야 난 검색 밖에 모른다. 문제를 어떤 식으로 풀어야 할 지는 알겠다.
- 주어진 숫자들에 다른 패턴으로
-와+를 붙여 나올 수 있는 모든 합을 구한다. - 구한 합들 중에서 타겟 넘버인 합의 개수를 센다.
근데 어떻게? 코드로 어떻게 표현해야 할 지를 몰라서 결국 오늘도 검색을 해봤다. 근데 가오가 있지 냅다 풀이 코드를 보기 싫었는데, 도저히.. 응용을 할 수가 없었다. 양심상 코틀린 말고 다른 언어의 풀이를 코틀린으로 풀어보자! 해서 파이썬 코드를 코틀린으로 바꾸는 작업만 해줬다.
class Solution {
var answer = 0
fun seek(i: Int, sum: Int, numbers: IntArray, target: Int) {
if (i == numbers.size) {
if (sum == target) answer += 1
return
}
seek(i+1, sum+numbers[i], numbers, target)
seek(i+1, sum-numbers[i], numbers, target)
}
fun solution(numbers: IntArray, target: Int): Int {
seek(0, 0, numbers, target)
return answer
}
}코드를 작성하고 나서 해석을 해본 건 다음과 같다.
- 저번 피로도 문제 풀이에서와 같이, 답을 저장할 변수를 클래스 전역으로 사용할 수 있게 선언해준다.
- 반복문 대신 재귀 함수를 이용해 숫자들의 합을 구한다.
- i는 탐색 횟수이자 현재 탐색하고 있는 인덱스를 의미한다.
- 탐색 횟수가 주어진 숫자들의 크기보다 크다면, 재귀를 탈출한다.
- 이 때 sum의 값을 확인해 타겟 넘버와 같은 값이라면 answer 값에 1을 더해준다.
- seek 함수의 재귀 호출 부분이 이해가 안 가서 직접 숫자를 넣어보며(...) 이해했다.
seek(0, 0, [1, 1, 1], 3): 처음 solution에서 호출- A:
seek(1, 1, [1, 1, 1], 3)와 B:seek(1, -1, [1, 1, 1], 3)호출 - A는
seek(2, 2, [1, 1, 1], 3)와seek(2, 0, [1, 1, 1], 3)호출 - B는
seek(2, 0, [1, 1, 1], 3)와seek(2, -2, [1, 1, 1], 3)호출 - ... 반복
⇒ 결국 배열 내 숫자들로부터 나올 수 있는 합의 모든 경우를 탐색하게 된다!
ex.[1, 1, 1],[1, 1, -1],[1, -1, 1],[1, -1, -1], ...
정말.. 혼자서는 절대 못 풀었을 것이다.
🔥 다른 사람의 풀이 1
위의 내가 푼 풀이를 보면 변하지도 않는 numbers 배열과 target 값을 계속 재귀 함수 호출 시에 넣어주고 있다. 이건 내가 코틀린의 함수를 중첩해서 사용할 수 있다는 사실을 몰랐기 때문이다. 원본 코드인 파이썬 코드에서는 다음 코드처럼 중첩해서 함수를 사용했다.
아직 나는.. 코틀린에 대해서 1도 모르는구나 싶었다. 다음번에는 중첩 함수도 꼭꼭 이용해봐야겠다.
class Solution {
fun solution(numbers: IntArray, target: Int): Int {
var answer = 0
fun dfs(sum: Int,idx: Int){
if(idx<numbers.size-1){
dfs(sum+numbers[idx],idx+1)
dfs(sum-numbers[idx],idx+1)
}
else{
if(sum+numbers[idx] == target) {answer++}
if(sum-numbers[idx] == target) {answer++}
}
}
dfs(0,0)
return answer
}
}😶🌫️ 다른 사람의 풀이 2
이 풀이 좀 보세요. 나는 이 풀이를 보고 내가 정말 멍청하다는 것을 깨달았다. 프로그래머스 문제 링크를 보면, 문제의 분류가 보이는데 바로 이 곳에 깊이/너비 우선 탐색(DFS/BFS)라고 적혀져 있었다. 나는 이 것만 보고 아! 이 문제는 꼭 탐색 알고리즘을 알고있고, 이해하고 있어야 풀 수 있겠구나! 라는 생각에 갇혀 코틀린스러운 방식을 생각하지 못했다.
코틀린의 함수들을 이용해서 이런 식으로도 풀 수 있다는 게 정말 놀라웠다. 사실 방식은 다 비슷해서 처음 그 방식을 생각하는 게 정말 어려운 것 같다.
class Solution {
fun solution(numbers: IntArray, target: Int): Int {
return numbers.fold(listOf(0)) { list, i ->
list.run {
map { it + i } + map { it - i }
}
}.count { it == target }
}
}💭 후기
알고리즘 공부 해야 된다!!! 꼭!!! 시간 남을 때 얼른 해놓자. 하우에버! 무서워.. 네버더레스! 해야 돼..
