프로그래머스 - 양궁대회(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92342

 

[문제 설명]

양궁대회에서 최선의 결과를 내는 방법

 

[접근 방법]

언뜻 보면 불가능한 완전탐색처럼 보인다.

1발을 쏘냐, 2발을 쏘냐, 3발을 쏘냐, ... , n발을 쏘냐 경우의 수가 굉장히 많이 나눠지는 느낌이다.

시간복잡도가 아마 10^n정도가 되지 않을까? 물론 화살의 개수는 계속 적어지므로 10^n보다는 확실히 작을 것이다.

 

그런데, 사실 그런 식으로 모든 경우를 구할 필요는 없다.

라이언이 아피치와 점수를 두고 겨룰 때 이기기 위해 필요한 전술은 2가지밖에 없다.

첫번째, 아피치 + 1발 맞추기 => 점수를 뺏을 수 있다.

두번째, 한발도 맞추지 않기 => 점수는 뺏기지만, 화살을 아껴서 후일을 도모할 수 있다.

따라서, 시간복잡도는 O(2^n) == 2^10 -> 굉장히 여유가 있는 완전탐색이다.

 

단, 이 문제는 까다로운 조건이 있다.

첫번째, 점수 차이를 최대한으로 내야 한다. 이건 그렇게 짜증나지 않다.

두번째, 이 조건이 굉장히 짜증난다. 낮은 점수를 더 많이 맞춘 경우가 더 우선이다.

 

나는 이 두 번째 조건을 제대로 파악하지 못해서 문제 푸는 데 시간을 많이 소비했다.

카카오 문제가 유난히 이런 함정을 많이 걸어놓아서 짜증난다.

 

class Solution {
    val answer = IntArray(11)
    var scoreDiffrence = 0

    fun solution(n: Int, info: IntArray): IntArray {
        recursion(info, IntArray(11), 0, n)

        return if (scoreDiffrence == 0) {
            intArrayOf(-1)
        } else {
            var cntOfArrow = 0
            answer.forEach { cntOfArrow += it }
            if (cntOfArrow != n) {
                answer[10] += n - cntOfArrow
            }

            answer
        }
    }

    private fun recursion(apacheShotInfo: IntArray, lionShotInfo: IntArray, idx: Int, remainArrowCnt: Int) {
        if (idx >= 11 || remainArrowCnt == 0) {
            var currentApacheScore = 0
            var currentLionScore = 0
            for (i in 0..10) {
                if (apacheShotInfo[i] > lionShotInfo[i]) {
                    currentApacheScore += 10 - i
                } else if (apacheShotInfo[i] < lionShotInfo[i]) {
                    currentLionScore += 10 - i
                } else {
                    if (apacheShotInfo[i] == 0) {
                        continue
                    }
                    currentApacheScore += 10 - i
                }
            }

            if (scoreDiffrence < currentLionScore - currentApacheScore) {
                scoreDiffrence = currentLionScore - currentApacheScore
                for (i in 0..10) {
                    answer[i] = lionShotInfo[i]
                }
                // else if : 같은 점수면, 누가 더 낮은 점수가 많은지 비교한다.
            } else if (scoreDiffrence == currentLionScore - currentApacheScore) {
                for (i in 10 downTo 0) {
                    if (answer[i] > lionShotInfo[i]) {
                        return
                    } else if (answer[i] < lionShotInfo[i]) {
                        scoreDiffrence = currentLionScore - currentApacheScore
                        for (i in 0..10) {
                            answer[i] = lionShotInfo[i]
                        }
                    }
                }
            }
            return
        }

        recursion(apacheShotInfo, lionShotInfo, idx + 1, remainArrowCnt)
        if (remainArrowCnt > apacheShotInfo[idx]) {
            lionShotInfo[idx] = apacheShotInfo[idx] + 1
            recursion(apacheShotInfo = apacheShotInfo, lionShotInfo = lionShotInfo, idx + 1, remainArrowCnt - apacheShotInfo[idx] - 1)
        }
        lionShotInfo[idx] = 0
    }
}

그러나, 사실 재귀 순서를 잘 조정하면 낮은 점수가 더 많은 사람을 계산할 필요가 없다.

역순으로 점수가 낮은 과녁부터 쏘는 재귀함수로 구현하면 처음 나온 '점수 최대차' 순서가 정답이다.

 

class Solution {
    val answer = IntArray(11)
    var scoreDifference = 0

    fun solution(n: Int, info: IntArray): IntArray {
        recursion(info, IntArray(11), 10, n)

        return if (scoreDifference == 0) {
            intArrayOf(-1)
        } else {
            var cntOfArrow = 0
            answer.forEach { cntOfArrow += it }
            if (cntOfArrow != n) {
                answer[10] += n - cntOfArrow
            }

            answer
        }
    }

    private fun recursion(apacheShotInfo: IntArray, lionShotInfo: IntArray, idx: Int, remainArrowCnt: Int) {
        if (idx < 0 || remainArrowCnt == 0) {
            var currentApacheScore = 0
            var currentLionScore = 0
            for (i in 0..10) {
                if (apacheShotInfo[i] > lionShotInfo[i]) {
                    currentApacheScore += 10 - i
                } else if (apacheShotInfo[i] < lionShotInfo[i]) {
                    currentLionScore += 10 - i
                } else {
                    if (apacheShotInfo[i] == 0) {
                        continue
                    }
                    currentApacheScore += 10 - i
                }
            }

            if (scoreDifference < currentLionScore - currentApacheScore) {
                scoreDifference = currentLionScore - currentApacheScore
                for (i in 0..10) {
                    answer[i] = lionShotInfo[i]
                }
            }
            return
        }


        if (remainArrowCnt > apacheShotInfo[idx]) {
            lionShotInfo[idx] = apacheShotInfo[idx] + 1
            recursion(apacheShotInfo = apacheShotInfo, lionShotInfo = lionShotInfo, idx - 1, remainArrowCnt - apacheShotInfo[idx] - 1)
        }
        lionShotInfo[idx] = 0
        recursion(apacheShotInfo, lionShotInfo, idx - 1, remainArrowCnt)
    }
}