[프로그래머스] 양궁대회

문제

프로그래머스

입력

 n:Int = 쏠 수있는 화살 개수
 info:[Int] = 어피치의 점수 0번째는 10점 과녁, 10번째는 0점 과녁이다. (역순)

출력

ans: [Int] = 어피치와 최대 점수차로 이길 수 있는 과녁 결과

1. 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.
2. 만약 점수차가 같은 최대  점수차 결과가 많을 시 적은 점수 과녁을 많이 쏜 것을 출력한다.

해석

1. 점수 계산 함수 필요

2. 쉽게 점수를 계산하려면 과녁판을 reversed 해야함. index와 점수를 매칭시키기 위해 

3. 화살을 쏠 수 있는 모든 조합을 구한다 (brute force)

4. 마지막에 점수 계산 시 사용한 최대 점수 차 과녁판 결과를 reversed해서 리턴한다.

 

코드

import Foundation

var apichResult: [Int] = []
var lionResult: [Int] = [Int](repeating:0, count:11)
var ans: [Int] = [-1]
var maxGap: Int = 0 
var duplicatedCheck: Set<[Int]> = .init()

func calcScore() {
    var lionScore = 0
    var apichScore = 0
    
    for i in 0..<11 {
        
        if apichResult[i] == 0 && lionResult[i] == 0 {
            continue
        }
        
        if apichResult[i] >= lionResult[i] {
            apichScore += i
        } else {
            lionScore += i
        }
        
    }
    
        
    if lionScore > apichScore && lionScore - apichScore >= maxGap  { 
        // 라이언이 이기고
        // 차이가 같다면 낮은 점수를 많이 맞춘 것이 우선이므로 >= 로 계속 업데이트 
        maxGap = lionScore - apichScore
        ans = lionResult
    }
    
}

func combination(_ index: Int, _ remainArrow: Int) {
    if remainArrow == 0 { // 남은 화살이 없다면 점수 계산 
        if duplicatedCheck.contains(lionResult) { return } // 이미 계산한 적 있으면 종료 
        duplicatedCheck.insert(lionResult) // 새로운 조합이면 set에 저장
        calcScore()
        return
    }
    
    if index >= 11 { // 0 ~ 10 까지니깐 종료
        return
    }
    
    for next in index+1..<12 { // 다음
        for arrow in 0...remainArrow { // 맞출 수 있는 활의 가짓수는 0발 ~ 가지고 있는 모든 발 
            
            // brute-force
            lionResult[index] = arrow 
            combination(next, remainArrow - arrow)
            lionResult[index] = 0
        }
    }
    
}


func solution(_ n:Int, _ info:[Int]) -> [Int] {
    
    apichResult = info.reversed()
    combination(0,n)
    
    
    return ans.reversed()
}