[프로그래머스] 2022 KAKAO BLIND RECRUITMENT 양궁대회 with Kotlin

문제

라이언과 아파치가 양궁 결승 대회를 한다.

라이언이 챔피언 타이틀을 갖고 있기 때문에 룰은 아파치에게 유리한 쪽으로 적용되었다.

 

과녁의 점수는 0점부터 10점까지 있으며, 선수는 각 n개의 화살을 지급받는다.

 

과녁에 맞춘 화살의 개수로 중복 없이 둘 중 한명만 각 점수를 얻을 수 있다.

화살의 개수가 같을 경우 아파치의 점수로 인정된다.

 

예를 들어 10점 과녁에 아차피가 2발, 라이언이 2발 맞췄다면, 아차피가 10점을 획득한다.

 

이때, 아파치가 점수 별로 화살을 맞춘 과녁이 배열로 주어졌을 때, 라이언이 아파치를 상대로 가장 큰 격차를 내서 이길 수 있는 경우를 반환하면 된다.

 

조건

• 화살은 모두 소진해야 한다.
• 만약 이길 수 없고, 지거나 비기는 경우뿐이라면 [-1]을 반환한다.
• 점수 차가 같은 여러가지 경우의 수가 나오면 낮은 점수의 과녁을 맞춘 경우를 반환한다.
  • 예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다
  • 다른 예로, [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.
• n: 화살의 개수,   info : 아파치가 맞춘 과녁 (왼쪽부터 10점)

 

입출력 예

n	info	result
5	[2,1,1,1,0,0,0,0,0,0,0]	[0,2,2,0,1,0,0,0,0,0,0]
1	[1,0,0,0,0,0,0,0,0,0,0]	[-1]
9	[0,0,1,2,0,1,1,1,1,1,1]	[1,1,2,0,1,2,2,0,0,0,0]
10	[0,0,0,0,0,0,0,0,3,4,3]	[1,1,1,1,1,1,1,1,0,0,2]

 

 

풀이과정

• 과녁 점수별로 모든 경우의 수를 확인해야 하므로 완전탐색 DFS
• 점수 별로 쏴야할 화살의 개수가 갖고 있는 화살의 개수보다 많으면 화살 소진 및 결과 배열에 저장
• 0번 과녁차례에 화살이 남았다면 0번에 모두 소진
• 재귀 함수시 이전 점수를 다시 접근하지 않도록 Boolean 배열 선언
• 화살이 모두 소진되었다면 각 결과 배열로 점수 계산하여 answer에 저장

 

코드

class Solution {
    val score = arrayOf(10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
    var answer: IntArray = intArrayOf()
    var scoreGap = 0
    
    fun solution(n: Int, info: IntArray): IntArray {
        
        Dfs(n, info, Array(11, {0}), Array(11, {false}))
        
        return if(answer.isEmpty()) intArrayOf(-1) else answer
    }
    
    // n : 남은 화살 개수 , info: info , rian: 라이언이 현재 맞춘 과녁 배열
    fun Dfs(n: Int, info: IntArray, rian: Array<Int>, target: Array<Boolean>){
        if(n <= 0){
            var apachScore = 0
            var rianScore = 0
            
            // 아파치와 라이언의 점수 확인
            for(i in info.indices){
                if(rian[i] == 0 && info[i] == 0) continue
                
                if(rian[i] > info[i]) rianScore += score[i]
                else apachScore += score[i]
            }
            
            // 라이언이 더 높다면 결과에 반영
            if(rianScore > apachScore) {
                
                // 점수 차가 더 많이 나는 결과로 
                if(rianScore - apachScore >= scoreGap){ 
                    answer = rian.toIntArray()
                    scoreGap = rianScore - apachScore
                }
            }
            
            return
        }
        
        for(i in info.indices){
            var arrow = n
            val r = rian.copyOf()
            if(target[i]) continue
            
            target[i] = true
            
            // 현재 과녁에 맞춰야할 화살 개수가 있다면
            if(arrow > info[i]){
                arrow -= info[i] + 1 // 화살 사용
                r[i] += info[i] + 1 // 라이언이 과녁에 맞춘 화살 개수 추가   
            }
            
            // 0점에서 화살이 남는다면 모두 소진
            if(i == 10){
                r[i] = arrow
                arrow = 0
            } 
            
            Dfs(arrow, info, r, target)
            target[i] = false
        }
        
    }
}