<프로그래머스> 타겟 넘버(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

문제를 보는데 다른 것보다 가장 먼저 눈에 들어온 건 좌측 상단에 써있는 '깊이/넓이 우선 탐색(DFS/BFS)'였다.

'이제 올 것이 왔구나...!!'

이전에 C, C++, Java로 문제를 풀 때마다 내 마음을 무너지게 만들었던 큰 벽 중에 하나라서 떨렸다.

이건 아직도 완벽히 뚫지 못한 주제다...

코테에 자주 나오는 유형이라서 나름 푸는 시간을 많이 가졌어도 다양한 유형으로 인해 매번 새롭다.

 

정신차리고 문제를 읽고서 처음 든 생각은 '조합인가...?'였다.

예시로 말하면 5개 중에 1개부터 5개를 선택하는 것만 하면 될 거 같았기 때문이다.

하지만 그렇게 하면 카테고리에 맞게 문제를 진행하지 않는 거라는 생각이 들어서 패스했다.

 

DFS, BFS로 고민하는데 쉽게 떠오르지 않더라

그래서 또 내가 생각하는 풀이의 순서를 그렸다.

가장 필요한 건 +, - 가 한 번씩 체크해야한다는 것이었다.

그래서 재귀(DFS)를 선택하게 되었고 코드를 짜는데... 매번 풀던 DFS문제가 2차원 배열이 대부분이어서 1차원 배열에서는 어떻게 해야하는지 감이 안 와서 멍때렸다.

 

그렇게 시간을 보내다가 끄적끄적하고 힌트와 이해가 동시에 찾아와서 해결할 수 있었다.

재귀로 쭉 들어가서 체크하고 나왔다 값 변경해서 다시 들어가고를 반복했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    var answer = 0
    fun solution(numbers: IntArray, target: Int): Int {
        dfs(numbers, 0, target)
        return answer
    }
    
    private fun dfs(numbers: IntArray, idx: Int, target: Int) {
        // 모든 숫자가 채워졌을 때
        if (idx == numbers.size) {
            if (numbers.sumOf { it } == target) answer++
            return
        }

        // 현재값을 +인 상태로 진행
        dfs(numbers, idx + 1, target)
        numbers[idx] *= -1
        // 현재값을 -인 상태로 진행
        dfs(numbers, idx + 1, target)
        numbers[idx] *= -1
    }
}

(지금보니까 이전에 풀었던 피로도 문제의 순열 구하는 것과 매우 흡사하다... 아님 말고)