문제
https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=kotlin
문제 풀이
굉장히 고생했던 문제이다.. 프로그래머스 특성상 디버깅이 쉽지가 않아, 재귀 함수를 사용하는데 항상 어려움을 겪고 있다.
출력을 통해서 디버깅을 하려고 해도, 재귀 함수의 깊이가 깊다면 출력내용 초과로 쉽지도 않다.
해당 문제를 푸는데 재귀를 어떤식으로 호출하는지가 중요하다.
재귀함수는 다음과 같은 흐름이다.
- 재귀함수는 깊이와 남은화살의 수를 가진다.
- 만약 깊이가 11보다 크다면 탐색을 중지한다.
- 만약 남은 화살의 수가 0이라면 화살을 다 쐈기 때문에 어피치와 라이언의 점수를 비교한다.
- 현재 재귀단계에서 어피치와 라이언의 점수차이가 더 크다면 점수차이를 반영하고, 결과 배열을 변경한다.
- 현재 재귀단계에서 어치피와 라이언의 점수차이가 같다면 문제 요구사항에 따라 더 적은 과녁을 많이 맞힌 방식으로 바꿔준다.
- 남은 화살수가 0이 아니라면, 과녁에 화살을 넣고, 재귀호출을 한다.
- depth를 +1하고, 잔여화살을 -i로 해준다.
- 재귀를 탈출하면 해당 과녁에 대한 화살 배정을 0으로 바꿔준다.
배열을 변경할때 바로 =을 넣어서 하면 될 줄 알았지만, 복사과정에서 깊은 복사가 실행돼서 변경사항이 모두 반영되기 때문에
배열이 기록이 되지 않아서 copyOf를 통해서 배열을 복사했다.
전체 코드
class Solution {
var score = 0
lateinit var result: IntArray
lateinit var rion: IntArray
fun solution(n: Int, info: IntArray): IntArray {
var answer: IntArray = IntArray(11){0}
result = IntArray(12) { 0 }
rion = IntArray(12) { 0 }
shotArrow(info, 0, n)
if (score == 0)
answer = intArrayOf(-1)
else {
for(i in 0 until 11){
answer[i]=result[i]
}
}
return answer
}
fun shotArrow(apeach: IntArray, depth: Int, res: Int) {
if(depth>11)
return
if (res == 0) {
val pair = compareScore(apeach)
if (score < pair.second - pair.first) { //점수차가 클 때
result = rion.copyOf()
score = pair.second - pair.first
} else if (score == pair.second - pair.first) { //점수차가 같을
for (i in 10 downTo 0) {
if (rion[i] > result[i]) {
result=rion.copyOf()
return
} else if (result[i] > rion[i]) { //기존 방법이 좋을 경우
return
}
}
}
} else {
for (i in 0..res) {
rion[depth] = i
shotArrow(apeach, depth + 1, res - i)
rion[depth] = 0
}
}
}
fun compareScore(apeach: IntArray): Pair<Int, Int> {
var apeachSum = 0
var rionSum = 0
for (i in 0 until 11) {
if (apeach[i] < rion[i]) { //라이온이 클땐 라이온이 점수를 먹음
rionSum += 10 - i
continue
}
if (apeach[i] == 0) //어피치가 0일 경우 넘어감.
continue
apeachSum += 10 - i
}
return Pair(apeachSum, rionSum)
}
}
'CodingTest > Programmers' 카테고리의 다른 글
프로그래머스[programmers] - N-Queen(Kotlin)[LV2] (0) | 2023.10.25 |
---|---|
프로그래머스[programmers] - 이모티콘 할인행사(Kotlin)[LV2] (2) | 2023.10.24 |
프로그래머스[programmers] - 합승 택시 요금(Kotlin)[LV3] (1) | 2023.10.19 |
프로그래머스[programmers] - N으로 표현(Kotlin)[LV2] (1) | 2023.10.06 |
프로그래머스[programmers] - 네트워크(Kotlin)[LV3] (0) | 2023.09.23 |