[Swift] 2022 KAKAO BLIND RECRUITMENT 양궁대회

 

Problem

 

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

---

Solution

 

해당 문제는 DFS 및 완전탐색 문제입니다.

 

1. 각 점수마다 이길지 질지를 결정한다.

 

10점부터 1점까지 어피치를 이길 수 있는지를 판별합니다.

 

만약 이길 수 있다면 해당 점수를 얻는 방법과 그냥 0발을 쏴서 다른 점수를 얻을 방법을 택합니다.

 

DFS를 사용해서 이기는 경우와 그냥 0발을 쏘고 다음 단계로 넘어갈 경우 2가지를 재귀해줍니다.

 

func dfs(leftArrow:Int,depth:Int,history:[Int],info:[Int]) {
    var newHistory = history
    var newLeftArrow = leftArrow
    
    ...
    
    if leftArrow > info[10-depth] {
        newLeftArrow -= info[10-depth]+1
        newHistory[depth] = info[10-depth]+1
        dfs(leftArrow: newLeftArrow, depth: depth-1, history: newHistory, info: info)
        newHistory[depth] = 0
    }
    
    dfs(leftArrow: leftArrow, depth: depth-1, history: newHistory, info: info)
}

 

 

2. 만약 화살이 남지 않았거나, 0점까지 온 경우 최대 점수와 비교해줍니다.

 

func dfs(leftArrow:Int,depth:Int,history:[Int],info:[Int]) {
    ...
    
    if depth == 0 || leftArrow <= 0 {
        newHistory[0] = depth == 0 ? leftArrow : newHistory[0]
        let score = getScoreGap(history,info)
        if maxScore == score {
            maxHistory.append(newHistory)
        }else if maxScore < score {
            maxScore = score
            maxHistory = [newHistory]
        }
        return
    }
    ...
}

 

* 어피치와 라이언의 점수 차이를 구하는 함수

 

func getScoreGap(_ history:[Int],_ info:[Int]) -> Int {
    var ryan = 0
    var apeach = 0
    for (i,s) in history.enumerated() {
           if s == 0 {
               if info[10-i] != 0 {
                   apeach += i
               }
           }else {
               ryan += i
           }
       }
    return ryan - apeach
}

 

3. 만약 최대 점수가 0보다 아래라면 [-1]을 반환합니다.

 

  if maxScore <= 0 {
        return [-1]
    }

 

4. 최대 점수가 0보다 크다면 낮은 점수가 많은 순으로 정렬한 첫 번째를 반환합니다.

 

func sortByMoreLowerScore() -> [Int]{
    var answer:[Int] = maxHistory.first!
    var max = 0
    for history in maxHistory {
        let numCount = history.filter{$0 != 0 }.count
        if max < numCount {
            answer = history
            max = numCount
        }
    }
    return answer.reversed()
}

---

Source Code