프로그래머스 [양궁대회] - js

양궁대회
https://programmers.co.kr/learn/courses/30/lessons/92342

주의할 점

• 어피치와 라이언이 맞춘 개수가 같다면 어피치의 승리
• 단, 둘 다 못마춘 경우라면 0점 처리
• 라이언이 가장 큰 점수차이로 이겨야 하며, 경우가 많다면 낮은 점수가 많은 경우가 답.

해결 방법

• dfs로 모든 경우를 탐색
• 0점부터 10점까지를 depth로 두고, 남은 화살개수만큼 반복하여 경우 체크
• 10점까지 확인하고, 모든 화살을 다 사용한 경우에 차이가 가장 큰 경우를 예비정답에 넣는다.
• 둘의 차이는 어피치가 크거나 같은 경우 "-" / 라이언이 큰 경우 "+" 하여 인자에 넣는다 (둘 다 0개를 맞춘 경우는 0점)

정답코드

const diffPoint = (apeche, rion) => {
    let result = 0;
    if (apeche >= rion) {
        result = -1
    } else {
        result = 1;
    }
    return apeche || rion ? result : 0;
}

const solution = (n, info) => {
    let answer = [];
    // 계산하기 쉽게 배열 뒤집음 (인덱스로 점수 계산 가능)
    info.reverse()

    // 가장 높은 차이를 저장하는 변수
    let bestDiff = 0;
    const findArrowPoints = (restArrowCount, pointArr, point, currentTotalDiffPoint) => {
        
        // 모든 점수를 훑은 경우
        if (point > 10) {
            // 남은 화살이 없고, 현재 점수차이가 기존의 점수차이보다 큰 경우
            if (!restArrowCount && currentTotalDiffPoint > bestDiff) {
                bestDiff = currentTotalDiffPoint;
                answer = [...pointArr].reverse()
            }
            return
        }

        // 남은 화살 개수 부터 시작해서, 사용하지 않을 경우까지 반복문
        for (let currentArrowCount=restArrowCount; currentArrowCount >= 0; currentArrowCount--) {
            const diffArrowCount = restArrowCount - currentArrowCount;
            const getPoint = diffPoint(info[point], currentArrowCount) * point;
            
            pointArr[point] += currentArrowCount;
            findArrowPoints(diffArrowCount, pointArr, point+1, currentTotalDiffPoint + getPoint)
            pointArr[point] -= currentArrowCount;
        }
    }

    // 배열 초기화
    const initArr = Array.from({length:11}, () => 0);
    // 인자: 남은 화살 개수, 쏜 화살을 저장하는 배열, 현재 확인 할 점수, 점수차이
    findArrowPoints(n, initArr, 0, 0);

    return answer.length ? answer : [-1];
}