[알고리즘 연습] 양궁대회 (프로그래머스 lv2, 스위프트)

문제

https://programmers.co.kr/learn/courses/30/lessons/92342

코딩테스트 연습 - 양궁대회

시도

import Foundation

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    var ascore = 0
    var rscore = 0

    var n = n
    var point: Float = 10

    var ap: [(Int,Float)] = info[0...10].map { 
        var result = $0 > 0 ? (Int(10-point), point*2 / Float($0 + 1)) : (Int(10-point), point / Float($0 + 1))
        point -= 1
        return result
    }.sorted(by: {
        $0.1 > $1.1
    })

    var shoot:[(Int,Int)] = ap.map { idx, point in
        if idx == 10 {
            return (idx, n)
        } else if info[idx] < n {
            rscore += (10-idx)
            n -= info[idx] + 1
            return (idx, info[idx] + 1)
        } else if info[idx] > 0 {
            ascore += (10-idx)
        } 
        return (idx, 0)
    }

    return ascore < rscore ? shoot.sorted(by: {
        $0.0 < $1.0
    }).map {
        $0.1
    } : [-1]
}

• 각 점수에 대한 기대값(=(얻을수있는점수+낮출수있는점수)/쏴야하는화살수)을 계산하고 이에 따라 순서대로 화살을 쏘는 방법입니다.
• 이 방법은 효율적이지만, '라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.'라는 조건을 지키지 못하기 때문에 많은 테스트 케이스에서 실패했습니다.

해결

import Foundation

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    var max_diff:Int = 0
    var max_lst:[Int] = []    
    var dfs = [(0,0,0,0,Array(repeating: 0, count:11))]
    
    while dfs.count > 0 {
        let now = dfs.removeLast()
        let ascore = now.0
        let lscore = now.1
        let idx = now.2
        let cnt = now.3
        var lst = now.4
        
        if cnt > n {
            continue    
        }
        
        if idx > 10 {
            let diff = lscore - ascore
            if diff > max_diff {
                lst[10] = n - cnt
                max_lst = lst
                max_diff = diff
            }
            continue
        }
        
        if info[10-idx] > 0 {
            dfs.append((ascore+idx, lscore, idx+1, cnt, lst))
        } else {
            dfs.append((ascore, lscore, idx+1, cnt, lst))
        }
        
        if cnt < n {
            lst[10-idx] = info[10-idx] + 1
            dfs.append((ascore, lscore+idx, idx+1, cnt+info[10-idx]+1, lst))
        }
    }    
    
    return max_diff == 0 ? [-1] : max_lst
}

• dfs로 가능한 모든 케이스를 탐색하는 방법입니다.
• 주어진 시간이 넉넉하길래 시도해봤는데 통과가 되었습니다.
• 각 idx를 돌면서 현재 idx에 해당하는 점수를 딸지, 따지 않을지로 나누어서 dfs에 넣습니다.
• 최종적으로는 max_diff가 갱신되지 않았거나 0으로만 갱신되었을 경우 [-1]을 리턴하도록 하고, 아닐 경우 max_lst를 리턴합니다.