[알고리즘] 양궁 대회(프로그래머스)

문제 링크

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

코드

private func checkScore(_ array: [Int]) -> [Int] {
    var apeachScore = 0
    var myScore = 0
    for i in array.indices {
        // 둘다 0점이아닌 경우
        if apeach[i] != 0 || array[i] != 0 {
            if apeach[i] >= array[i] {   // 어피치가 같거나 큰 경우
                apeachScore += 10 - i
            } else if apeach[i] < array[i] {    // 내가 점수가 큰 경우
                myScore += 10 - i
            }
        }
            
    }
    return [apeachScore, myScore]
}

private func dfs(_ position: Int, _ array: [Int], _ n: Int) {
    
    // 화살을 전부다 쐈을 때 이겼는지 점수계산
    if n == 0 {
        let score = checkScore(array)
        // (점수가 최고 점수차랑 같거나 큰 경우 || 처음 들어온 경우) && 라이언이 점수가 더 높을 때
        if ((score[1] - score[0] >= difference) || (difference == -1)) && score[1] > score[0] {
            // 처음 점수를 추가하거나, 점수차이가 지금 가지고있는 점수차보다 큰 경우
            if resultArray == [-1] || score[1] - score[0] > difference {
                resultArray = array
                difference = score[1] - score[0]
            } else {    // 점수가 같은 경우
                var check = false
                    // 점수가 낮은 화살을 누가 더 많이 쐈는지 검사
                    for i in stride(from: 10, to: -1, by: -1) {
                        if resultArray[i] < array[i] {
                            check = true
                            break
                        } else if resultArray[i] > array[i] {
                            break
                        }
                    }

                if check {
                    resultArray = array
                    difference = score[1] - score[0]
                }
            }
        }
        return
    }
    
    // index가 벗어났을 때 남은 화살 개수가 있다면 return
    if position > 10 && n > 0 {
        return
    }
    
    // 다음 과녁으로 넘어가는 것
    for i in 0...n {
        // 쏠 화살 개수가 남아있다면
        if n - i >= 0 {
            var temp = array
            temp[position] = i
            dfs(position + 1, temp, n - i)
        }
    }
}

var apeach = [Int]()
var resultArray = [-1]
var difference = -1
func solution(_ n:Int, _ info:[Int]) -> [Int] {
    apeach = info
    
    let array = Array(repeating: 0, count: 11)
    dfs(0, array, n)
    
    return resultArray
}

풀이

DFS를 사용하여 문제풀이를 진행했습니다.

우선 아래 전역 변수 3개를 선언합니다.

var apeach = [Int]()	// 어피치 양궁 점수
var resultArray = [-1]	// 결과값 배열
var difference = -1	// 어피치와 점수 차이

solution함수에서 DFS 함수를 호출합니다.

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    apeach = info
    
    let array = Array(repeating: 0, count: 11)
    dfs(0, array, n)
    
    return resultArray
}

DFS 함수는 아래와 같습니다.

현재 position이 A일 때 0~n개의 화살을 쏜 후 A + 1로 재귀 호출합니다.

화살을 전부 다 쐈을 때는 어피치와 점수를 비교해 점수차가 더 높다면 resultArray, difference 변수를 업데이트합니다.

position이 10을 넘어갔을 때 화살을 전부 다 쏘지않았다면 더 이상 재귀 호출을 수행하지 않습니다.

private func dfs(_ position: Int, _ array: [Int], _ n: Int) {
    
    // 화살을 전부다 쐈을 때 이겼는지 점수계산
    if n == 0 {
        let score = checkScore(array)
        // (점수가 최고 점수차랑 같거나 큰 경우 || 처음 들어온 경우) && 라이언이 점수가 더 높을 때
        if ((score[1] - score[0] >= difference) || (difference == -1)) && score[1] > score[0] {
            // 처음 점수를 추가하거나, 점수차이가 지금 가지고있는 점수차보다 큰 경우
            if resultArray == [-1] || score[1] - score[0] > difference {
                resultArray = array
                difference = score[1] - score[0]
            } else {    // 점수가 같은 경우
                var check = false
                    // 점수가 낮은 화살을 누가 더 많이 쐈는지 검사
                    for i in stride(from: 10, to: -1, by: -1) {
                        if resultArray[i] < array[i] {
                            check = true
                            break
                        } else if resultArray[i] > array[i] {
                            break
                        }
                    }

                if check {
                    resultArray = array
                    difference = score[1] - score[0]
                }
            }
        }
        return
    }
    
    // index가 벗어났을 때 남은 화살 개수가 있다면 return
    if position > 10 && n > 0 {
        return
    }
    
    // 다음 과녁으로 넘어가는 것
    for i in 0...n {
        // 쏠 화살 개수가 남아있다면
        if n - i >= 0 {
            var temp = array
            temp[position] = i
            dfs(position + 1, temp, n - i)
        }
    }
}

화살을 n개 모두 쐈을 때 어피치와 점수를 비교하기 위해 아래 함수를 작성했습니다.

private func checkScore(_ array: [Int]) -> [Int] {
    var apeachScore = 0
    var myScore = 0
    for i in array.indices {
        // 둘다 0점이아닌 경우
        if apeach[i] != 0 || array[i] != 0 {
            if apeach[i] >= array[i] {   // 어피치가 같거나 큰 경우
                apeachScore += 10 - i
            } else if apeach[i] < array[i] {    // 내가 점수가 큰 경우
                myScore += 10 - i
            }
        }
            
    }
    return [apeachScore, myScore]
}