코딩테스트 준비(kotlin)/DFS, BFS
[프로그래머스, kotlin] 타겟넘버
1chanhue1
2024. 6. 28. 17:28
재귀를 이용한 문제 풀이
fun solution(numbers: IntArray, target: Int): Int {
var answer=0
fun dfs(index: Int, currentSum: Int) {
if (index == numbers.size) {
if (currentSum == target) {
answer = answer + 1
}
} else {
val add = dfs(index + 1, currentSum + numbers[index])
val subtract = dfs(index + 1, currentSum - numbers[index])
}
}
dfs(0, 0)
return answer
}
간단한 시나리오 예시
numbers = intArrayOf(1, 2), target = 1 일 경우 numbers 배열은 [1, 2]이고, 목표 값 target은 1입니다.
전체 실행 트리
시나리오 결과 : 경우의 수는 1개로 answer 값은 1
스택(리스트)을 이용한 문제 풀이
fun solution(numbers: IntArray, target: Int): Int {
val stack = mutableListOf<Pair<Int, Int>>() // (index, currentSum)
stack.add(Pair(0, 0)) // 초기 상태 추가
var count = 0
while (stack.isNotEmpty()) {
val (index, currentSum) = stack.removeAt(stack.size - 1)
if (index == numbers.size) {
if (currentSum == target) {
count++
}
} else {
stack.add(Pair(index + 1, currentSum + numbers[index]))
stack.add(Pair(index + 1, currentSum - numbers[index]))
}
}
return count
}
느낀점 : DFS 풀이 방법은 재귀, 스택 두가지 방법이 있지만 재귀로 코드를 구성하는 게 항상 어려운 것 같다.
문제를 많이 풀어보고 익숙해 지도록 노력해야겠다.