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

요구능력 : 백트래킹

 

코드설명 : 

 

문제를 잘 읽어야한다.

핵심적인 부분만 찝어보면

1) k점을 어피치가 a발 맞추고 라이언이 b발 맞췃는데 a >= b이면 어피치가 k점을 가져간다.

2) k점을 여러번 맞혀도 k점만 가져감, a = b = 0인 경우 둘 다 못가져간다.

3) 최종점수가 같을 경우 어피치가 우승자

4) 라이언이 어피치를 가장 큰 점수차이로 이기려고 한다.

5) 라이언이 우승 못하는경우 (지거나 비기는경우) -1리턴

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

 

문제의 설명을 읽고 입출력 예를 보고 나서 이 문제가 백트래킹 문제라는 것을 파악했다.

6) 조건을 보면 가장 낮은 점수를 더 많이 맞힌 경우를 return하라고 해서 낮은점수부터 백트래킹을 시작했다.

4) 그리고 더 높은 점수가 나오면 교체하고 그렇지 않으면 교체하지 않았다.

낮은점수부터 백트래킹 하지않으면 낮은 점수로 이루어진 result보다 높은점수로 이루어진 result가 먼저들어가게된다.

(이 부분은 하고싶은대로 하면될것같다.)

 

 그리고 시간복잡도가 그렇게 높지않으므로 화살을 다쐇을때 라이언이 쏜 과녁의 배열과 어피치가 쏜 과녁의 배열을 돌면서 1), 2), 3) 4)조건을 만족해줬고, 라이언이 우승 못하는 경우는 lionWin변수를 처음에 false로 두고 lisonSum(라이언이 쏜 과녁의 합)이 appeachSum보다 큰적이 한번이라도 있으면 라이언이 우승할 수 있는 경우이므로 lionWin을 true로 두었다.

 

후기 : 문제 빠르게 접근잘하고 잘 풀었는데 순열인지 선택인지 헷갈려서 둘다해봤더니 선택이되서 선택을썻다.

이거판단하는 연습좀해야겠다..

아! 그리고 "프로그래머스 컴파일러는 함수를 아래에 정의하고 위에서 쓰면 컴파일에러가 발생한다"

나름 혼자터득했다..

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    var result = Array(repeating: 0, count: 11)
    var arr = Array(repeating: 0, count: 11)
    var lionSum = 0
    var appeachSum = 0
    var temp = 0 //점수차이 계산
    var lionWin = false
    func dfs(_ depth: Int, _ start: Int){
        if depth == n{
            lionSum = 0
            appeachSum = 0
            for i in 0...10{
                if arr[i] == 0 && info[i] == 0 {
                    continue
                }
                if info[i] < arr[i]{
                    lionSum += 10 - i
                }else{
                    appeachSum += 10 - i
                }
            }
            if lionSum > appeachSum{
                lionWin = true
                if lionSum - appeachSum > temp{
                    result = arr
                    temp = lionSum - appeachSum
                }
            }
            return
        }
        
        for i in start...10{
            arr[10 - i] += 1
            dfs(depth + 1, i)
            arr[10 - i] -= 1
        }
    }
    dfs(0, 0)
    if !lionWin{
        result = [-1]
    }
    return result
}