[Swift 알고리즘] 프로그래머스(Lv.2) - 양궁 대회 / 2022 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 양궁 대회" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 dfs + 완전 탐색 문제입니다.

 

1. 점수판을 초기화하고 dfs를 시작합니다.

라이언의 점수판을 0으로 초기화하여 dfs를 시작합니다.

 

var lionHistory: [Int] = Array(repeating: 0, count: 11)
dfs(lionHistory, info.reversed(), depth: 10, arrow: n) //info도 0~10으로 전달

이번 문제는 낮은 점수를 많이 맞춘 사람을 기준으로 정렬해야 합니다.

따라서 점수를 저장할 때 0~10 순서로 저장할 것입니다.

index의 통일을 위해 info도 역순으로 전달했습니다.

 

2. DFS + 완전 탐색 로직

DFS + 완전 탐색 로직의 핵심은 어피치를 이기느냐 지느냐입니다.

• 해당 점수를 얻는 경우(어피치보다 많은 화살을 쏘는 경우)
• 해당 점수를 얻지 않는 경우(어피치보다 많은 화살을 못 쏘는 경우, 그냥 안 쏘는 경우)

위 두 가지를 탐색하여 2^10 가지 경우를 탐색하는 것입니다.

 

2-1. DFS의 종료 조건

if depth == 0 || arrow <= 0 { //10번째 시도 || 화살을 다 쏨
    copyHistory[0] = depth == 0 ? arrow : copyHistory[0]
    let score = getScoreGap(history, info) //점수차 확인
    if maxScore == score { //최대 점수 차이면 점수판 저장
        maxHistory.append(copyHistory)
    } else if maxScore < score { //최대 점수 갱신
        maxScore = score
        maxHistory = [copyHistory]
    }

    return
}

DFS의 종료 조건먼저 살펴보겠습니다.

1. 10개의 점수를 모두 살펴본 경우
2. 화살이 다 떨어진 경우

위 두 가지 경우인 경우 어피치와 라이언의 점수차를 구합니다.

• 점수차 == 현재 최대 점수 : 점수판을 추가합니다.
• 점수차 > 현재 최대 점수 : 최대 점수와 점수판을 갱신합니다.
• 점수차 < 현재 최대 점수 : 아무 동작을 하지 않습니다.

점수판을 저장하는 이유는 4번에서 설명합니다.

 

2-2. 해당 점수를 얻는 경우

여기서 해당 점수를 나타내는 인자는 depth 입니다.

dfs 시작을 10으로 했으므로 10점부터 9점, 8점 ... 0점 순서로 확인합니다.

let shooting = info[depth] + 1
if arrow >= shooting { //어피치를 이길 수 있는 경우
    copyArrow -= shooting
    copyHistory[depth] = shooting //쏜 경우

    dfs(copyHistory, info, depth: depth - 1, arrow: copyArrow) //다음 점수로 이동

    copyHistory[depth] = 0 
}

점수를 얻을 수 있는 경우는 남은 화살 수 >= 어피치가 쏜 화살 수 + 1 일 때 입니다.

이때는 점수판에 표시하고 남은 화살 수에서 (어피치가 쏜 화살 수 + 1)을 빼서 다음 점수로 dfs 탐색을 합니다.

탐색을 종료하고 되돌아오면 점수판 표시를 지웁니다.

 

2-3. 해당 점수를 얻지 않는 경우

화살이 부족해 어피치를 이기지 못하거나 화살이 충분해도 그냥 안 쏘는 경우를 탐색합니다.

dfs(copyHistory, info, depth: depth - 1, arrow: arrow)

arrow와 점수판은 그대로 설정하고 depth만 줄여 dfs 탐색 합니다.

 

3. 어피치를 못 이기는 경우를 처리합니다.

최대 점수가 전혀 갱신이 안 되었다면 어피치를 이기지 못하는 경우입니다.

이때는 [-1]을 return 합니다.

 

4. 어피치를 이기는 경우를 처리합니다.

어피치를 이길 수 있는 경우, 최대 점수 차로 이겨야 하며 그중에서도 낮은 점수를 많이 맞춘 경우를 return 해야 합니다.

그래서 2-1에서 점수판을 저장해둔 것입니다.

 

점수판을 낮은 점수를 많이 맞춘 것으로 오름차순 정렬합니다.

maxHistory.sort { 
    $0.filter { $0 != 0 }.count > $1.filter { $0 != 0 }.count
}

같은 화살 개수이고 맞춘 점수가 같을 때 낮은 점수를 많이 맞췄다는 것은 맞춘 점수의 스펙트럼이 넓다는 것을 의미합니다.

 

예를 들어, 화살이 5개인 경우 1점에 5개를 맞춘 것과 5점에 1개 0점에 4개를 맞출 수 있습니다.

0점을 더 많이 맞춘 후자의 경우 5, 0으로 맞춘 점수의 종류가 더 많습니다.

 

이 원리로 2차원 배열을 sort 합니다.

 

5. 역순 배열을 return 합니다.

점수 비교의 편의를 위해 0 ~ 10점 순서로 작업을 했었습니다.

문제에서 요구하는 것은 10 ~ 0점 순서이므로 역순 배열을 반환합니다.

 

후기

문제의 원리 자체는 쉬우나 코드를 짜기 어려웠던 문제였습니다.

왜 2레벨인지 모르겠는... 그런 문제였습니다 ㅠㅠ

 

감사합니다!

 

 

---

전체 코드

import Foundation

var maxHistory: [[Int]] = [] //최대 점수 차이인 점수판 
var maxScore: Int = -1 //최대 점수 차이

func dfs(_ history: [Int], _ info: [Int], depth: Int, arrow: Int) {
    var copyHistory = history
    var copyArrow = arrow
    
    if depth == 0 || arrow <= 0 { //10번째 시도 || 화살을 다 쏨
        copyHistory[0] = depth == 0 ? arrow : copyHistory[0]
        let score = getScoreGap(history, info) //점수차 확인
        if maxScore == score { //최대 점수 차이면 점수판 저장
            maxHistory.append(copyHistory)
        } else if maxScore < score { //최대 점수 갱신
            maxScore = score
            maxHistory = [copyHistory]
        }
        
        return
    }
    
    let shooting = info[depth] + 1
    if arrow >= shooting { //어피치를 이길 수 있는 경우
        copyArrow -= shooting
        copyHistory[depth] = shooting //쏜 경우
        
        dfs(copyHistory, info, depth: depth - 1, arrow: copyArrow) //다음 점수로 이동
        
        copyHistory[depth] = 0 
    }
    
    //안 쏜 경우
    dfs(copyHistory, info, depth: depth - 1, arrow: arrow)
}

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

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    var result: [Int] = []
    
    var lionHistory: [Int] = Array(repeating: 0, count: 11)
    dfs(lionHistory, info.reversed(), depth: 10, arrow: n) //info도 0~10으로 전달
    
    // print("maxScore: \(maxScore) / maxHistory: \(maxHistory)")
    guard maxScore > 0 else { //못 이기는 경우
        return [-1]
    }

    //같은 점수일 때 적은 점수에 많이 쏜거면 쏜 점수의 종류가 많다.
    maxHistory.sort { 
        $0.filter { $0 != 0 }.count > $1.filter { $0 != 0 }.count
    }
    
    // print("maxHisotry: \(maxHistory)")
    return maxHistory.first!.reversed()
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.