[프로그래머스/Lv.2] Swift - 양궁대회

2025.03.15 기준 Level 2
https://school.programmers.co.kr/learn/courses/30/lessons/92342

알고리즘

브루트포스

문제 요약

- 어피치가 화살을 n발 쏜 상태로 라이언이 화살 n발을 쏜다.

- 점수를 계산한다.

1. k(1~10사이의 자연수)점을 어피치가 a발을 맞히고, 라이언이 b발을 맞혔을 때,
2. a >= b인 경우 어피치가 k점을 가져간다.
3. a < b인 경우 라이언이 k점을 가져간다.
4. a == b == 0인 경우 아무도 점수를 획득하지 않는다.

ex) 어피치가 10점을 2발, 라이언도 10점을 2발 맞힌 경우 어피치가 10점 획득

ex) 어피치가 10점을 0발, 라이언이 10점을 2발 맞힌 경우 라이언이 10점 획득

 

- 최종 점수가 더 높은 선수가 우승(단, 최종점수가 같으면 어피치가 우승)

- 라이언이 가장 큰 점수 차이로 이기기 위해 n발을 어떻게 맞혀야 하는지 구하시오.

- 만약 라이언이 이길 수 없는 경우 [-1]을 리턴

 

제약 조건

info: [Int], 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 배열

n: 라이언이 쏘아야하는 화살 개수

• 1 <= n <= 10
• info.count == 1
• 0 <= info의 원소값 <= n
• info 원소의 총합 == n
• info[i] = 10-i점을 맞힌 화살 개수

 

- 라이언은 반드시 n발을 모두 쏘아야 함.

- 라이언이 가장 큰 점수차이로 우승할 수 있는 방법이 여러가지인 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return

ex) [2, 3, 1, 0, 0, 0, 0, 1, 3, 0, 0]과 [2, 1, 0, 2, 0, 0, 0, 2, 3, 0, 0]을 비교하면 후자를 return

아이디어

1. 쏘아야하는 화살의 최대 개수도 10개이고, 과녁의 개수도 11개이기 때문에 완전탐색이 가능하다고 생각함.
2. dfs 완전탐색을 통해 각 점수에서 쏘아야하는 화살의 개수를 차례로 넣어봄
3. 만약 화살의 개수가 남은 화살 개수보다 적다면 경우의 수에서 제외
4. 만들어진 경우의 수에서 라이언이 n발을 쏘았는지 확인(getScoreDiff)
5. n발을 쏘았다면 어피치와의 점수차를 계산해서 라이언이 이긴 경우 점수차를 반환하고 그렇지 않으면 0을 반환(getScoreDiff)
6. 정답 후보 배열에 4, 5번 조건을 통과한 경우의 수를 저장함.
7. 정답 후보 배열에서 점수 차가 큰 순으로 정렬
8. 만약 점수 차가 같다면 배열의 뒷부분부터 확인하여 작은 점수를 많이 쏜 경우가 더 앞으로 가게 정렬

풀이

// 브루트포스

import Foundation

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    var ryan: [Int] = []
    var arrow = n
    var candidate: [[Int]] = []

    func dfs(_ count: Int, _ score: inout [Int], _ remain: inout Int) {
        if score.count == 11 {              // 라이언의 점수판이 완성되고 라이언이 승리하는 경우만 추출
            let diff = getScoreDiff(score, info)
            if diff != 0 {                  // 라이언이 이긴 경우
                candidate.append(score + [diff])
            }
            return
        }
        
        for i in 0...n {                    // 0개부터 n개까지 활 쏘기 가능
            if i > remain {                 // 남는 화살이 없다면 쏘지 않음
                continue
            } else {
                score.append(i)             // 남는 화살이 있는 경우 활 쏘기
                remain -= i
                dfs(count+1, &score, &remain)
            }
            remain += score.removeLast()    // 다시 뽑은 화살만큼 더해주기
            
        }
    }
    
    func getScoreDiff(_ ryan: [Int], _ apeach: [Int]) -> Int {
        if ryan.reduce(0, +) != n { return 0 }            // 라이언이 쏜 화살의 개수도 n개여야 함
        var rScore = 0
        var aScore = 0
        
        for i in 0..<11 {
            if ryan[i] == 0 && apeach[i] == 0 {               // 둘 다 획득하지 못하는 경우
                continue
            }
            if ryan[i] > apeach[i] {                          // 라이언이 획득하는 경우
                rScore += (10-i)
            } else {                                          // 어피치가 획득하는 경우
                aScore += (10-i)
            }
        }

        return rScore > aScore ? rScore - aScore : 0           // 라이언이 이긴 경우 두 점수 차 반환
    }
    
    dfs(0, &ryan, &arrow)
    
    // 점수 차가 가장 큰 순 -> 작은 점수를 많이 맞춘 순
    candidate.sort{
        if $0.last! == $1.last! {                               // 점수 차가 같은 경우
            for i in (0..<11).reversed() {                      // 역순으로 비교하여 더 많이 쏜 경우를 우선 정렬
                if $0[i] != $1[i] { return $0[i] > $1[i] }
            }
        }
        return $0.last! > $1.last!                              // 점수차가 큰 순으로 정렬
    }
    
    return candidate.isEmpty ? [-1] : candidate[0].dropLast(1)
}