[프로그래머스] 양궁대회 (Swift) (스터디)

https://programmers.co.kr/learn/courses/30/lessons/92342

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

1. 적용 알고리즘과 문제 설명

적용 알고리즘 : dfs 깊이 우선 탐색

문제 설명

어피치와 라이언이 양궁 시합을 한다.

점수는 과녁의 점수 영역에 누구의 화살이 더 많이 있는지에 따라 더 많이 맞힌 사람이 그 점수를 얻는다.

만약에 동일한 개수로 맞혔다면 어피치가 점수를 얻는다.

 

어피치의 결과판이 주어진다. 이때 라이언이 어떻게 경기를 해야 (각 점수영역에 화살을 몇개 맞혀야) 가장 높은 점수차로 이길 수 있는지

라이언의 결과판 하나를 반환하는 문제이다.

 

단, 라이언이 가장 큰 격차로 이길 경우가 여러개라면 가장 낮은 점수를 더 많이 맞혔을 때가 최종 결과이다.

 

접근 방법

어피치의 점수를 보고 라이언 입장에서 이 점수를 따는 데에 화살을 쓸지, 아니면 그냥 점수를 포기할지 두가지 경우로 나뉘어진다.

따라서 하나의 점수 영역에 대해 어피치 화살보다 1개를 더 맞혀서 점수를 얻느냐, 화살을 쏘지 않고 (0개의 화살) 점수를 포기하느냐 이다.

모든 경우를 탐색하여 라이언이 가장 큰 격차로 이기는 경우만 라이언의 결과표를 저장한다.

현재까지 가장 큰 격차와 지금 새로 나온 격차가 같으면 배열의 배열에 append해준다.

dfs함수를 마치면 가장 큰 격차를 얻을 수 있는 라이언의 점수판의 경우의수가 담긴 배열이 만들어진다.

결과로는 하나의 경우만 반환해야 하므로 만약 경우가 여러개라면 그 중 하나를 선별하는 작업이 필요하다.

그 작업을 하는 함수가 getResult()이다.

 

getResult()는 각 배열의 마지막 원소(가장 점수가 낮은 영역의 화살 수)부터 크기를 비교한다.

map을 사용하여 모든 배열의 해당 위치 원소 중 가장 큰 값을 구하고, 이 값과 같은 배열만 filtering한다.

가장 낮은 점수에 있는 화살의 수가 같을 경우 그 다음으로 낮은 점수의 화살수를 비교해야 하기 때문이다.

이 과정을 resultCandis(라이언의 점수판 경우를 담아둔 배열)의 원소가 하나일 때 까지 반복한다.

 

단, 라이언이 이길 수 있는 경우가 없다면 resultCandis배열의 원소가 0이므로 주의해야한다.

 

2. 코드에 대한 설명

코드에 대한 상세한 설명은 주석으로 대신했다.

import Foundation

var resultCandis:[[Int]] = []
func getResult() {
	// 여기서 i는 현재 비교하고자 하는 '가장 낮은 점수'를 가리킨다.
    for i in stride(from: 10, to: 0, by: -1) {
        if resultCandis.count == 1  {
            return
        }
        let max:Int = resultCandis.map{ $0[i] }.max() ?? 0
        resultCandis = resultCandis.filter{ $0[i] == max }
    }
}

var maxGap:Int = 0
var infoA:[Int] = [] // 어피치의 점수판
func dfs(_ i:Int, _ n:Int, _ rArr:[Int], _ rScore:Int, _ aScore:Int) {
	// 10번째 영역(0점 영역)까지 도달하면 라이언의 경기의 모든 경우를 나타내는 트리의 leaf노드에 도달했다는 뜻이므로 남은 화살을 모두 사용한다. 
    // 남은 함수를 모두 0점에 놓는 이유는 가장 낮은 점수를 많이 맞히는 것이 유리하기 때문이다.
    if i == 10 {
        let gap = rScore - aScore
        if gap > 0 {
            if gap > maxGap {
                maxGap = gap
                resultCandis = [rArr+[n]]
            } else if gap == maxGap {
                resultCandis.append(rArr+[n])
            }
        }
        return
    }
    
    let winNum:Int = infoA[i]+1 
    // 라이언이 점수를 획득하는 경우 (이길 수 있는 화살이 남아있을 때만 가능)
    if n >= winNum {
        dfs(i+1, n-winNum, rArr+[winNum], rScore + 10 - i, aScore)
    }
    // 라이언이 점수를 획득하지 않는 경우 (만약 둘다 0개의 화살을 맞혔다면 둘다 점수를 얻지 못함
    let aPoint:Int = infoA[i] == 0 ? 0 : 10 - i
    dfs(i+1, n, rArr+[0], rScore, aScore + aPoint)
}

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    infoA = info
    
    dfs(0, n, [], 0, 0)
    
    if resultCandis.isEmpty {
        return [-1]
    } else {
        getResult() // resultCandis에 하나만 남기기 위한 함수 호출
        return resultCandis[0]    
    }
}

3. 시간 복잡도, 공간 복잡도 계산

이게 뭐냐면 DFS 최대 호출 횟수 = 2047

dfs호출 횟수는 트리의 노드수와 같다.

중간에 화살이 부족하면 이보다 더 적은 수를 호출하겠지만 최악의 경우는 이렇다!

여기서 n이 0부터 10까지 가는 것은 과녁의 점수 영역을 나타낸다.

 

그리고 라이언의 경우의 수는 리프노드의 개수로 최대 2^10개 이다.

따라서 resultCandis에 담길 수 있는 배열의 수도 2^10개

getResult함수에서 최악의 경우 0점부터 10점까지 검토하게 된다면 반복문을 11번 돌게 된다.

filter와 map 고차함수를 사용하므로 for 문 안에서는 최악의 경우 2*1024이다.

따라서 11 * 2 * 1024 = 11 * 2^11

 

고로..2047 + 11 * 2^11 = 24575 가 최악의 시간으로 고정된다.

최악의 시간 복잡도인데 과녁 점수판이 10점까지로 고정되어있으므로

화살의 수가 몇개인지에 영향을 받지는 않는다.. 흠

 

공간복잡도는

원소를 11개 담고 있는 배열이 2^10개 생길 수 있고,

이를 담은 resultCandis도 존재하므로 2^11 정도 된다..

 

4. 사용 라이브러리

Array의 append() 메서드 : O(1)

 

5. 문제 풀이에 어려웠던 점

dfs 로직을 도출하는 과정

결과를 하나만 도출하는 getResult() 함수 구현에서 처음에는 배열의 원소를 지워가며 하나가 남을 때 까지 반복하려 했는데

로직에 오류가 있어서 실패했다. 그리고 시간은 더 소요할거라고 생각되는 map과 filter를 사용하여 해결함.

 

어느정도 풀이한 후에 둘다 0개를 맞힐경우 0점으로 처리를 안해줘서 디버깅하여 수정했다.

또 배열이 비어있는 경우에 getResult()함수를 호출하게 되어서 접근오류가 났었다.