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

문제 설명

라이언과 어피치가 양궁대회에 참여했다. 어피치는 이미 화살을 쏜 상태고 어피치가 쏜 화살의 수와 점수가 주어진다. 점수를 매기는 조건에 따라 라이언이 이길 수 있는 경우 중 어피치와의 점수 차가 최대가 되는 경우를 출력하면 된다. 점수 차가 최대가 되는 경우가 여러 개인 경우 가장 낮은 점수를 많이 맞힌 경우를 출력한다. 만약 라이언이 이길 수 없는 경우에는 [-1]을 리턴해야 한다.

점수를 매기는 조건은 특정 점수를 많이 쏜 사람이 해당 점수를 가져가는 식이다. 여기에도 조건이 있다. 만약 특정 점수를 똑같이 쐈을 경우에는 어피치가 점수를 가져간다. 그리고 한 발도 맞히지 못한 경우 둘 다 점수를 가져가지 못한다.

문제 풀이

조합, 완전탐색, 정렬을 이용해서 문제를 풀었다.
우선, dfs를 사용해서 라이언이 쏠 수 있는 경우의 수를 모두 구했다. (1)
그리고 그 경우의 수를 모두 탐색하면서 라이언, 어피치의 점수를 구하고 둘의 점수 차이가 최대가 되는 경우를 구했다.(2) 그리고 그렇게 구해진 경우들이 둘 이상인 경우에는 정렬을 통해서 가장 낮은 점수를 많이 맞힌 경우를 출력했다.(3)

function solution(n, info) {
    let answer = []
    let max = -Infinity
    // (1) 라이언이 쏠 수 있는 경우의 수를 구하는 dfs
    // 라이언이 쏠 수 있는 경우의 수를 arr 배열에 담는다.
    const arr = []
    const dfs = (depth,start,path) => {
        if (depth === n) {
            arr.push(path)
            return
        }
        for (let i = start; i < 11; i++) {
            dfs(depth+1,i,[...path,i])
        }
    }
    dfs(0,0,[])
  	// (2) dfs를 통해 구한 경우의 수마다 어피치와 라이언의 점수 차를 구한다.
  	// 점수 차가 최대가 되는 경우를 answer 배열에 담고, max 값을 갱신한다.
    for (let i = 0; i < arr.length; i++) {
        let apeach = 0
        let lion = 0
        const temp = Array(11).fill(0)
        for (let j = 0; j < arr[i].length; j++) {
            temp[arr[i][j]]++
        }
        for (let l = 0; l < 11; l++) {
            if (info[l] === 0 && temp[l] === 0) {
                continue
            }
            
            if (info[l] - temp[l] >= 0) {
                apeach += 10 - l
            }   else {
                lion += 10 - l
            }
        }
        if (lion > apeach && lion - apeach === max) {
            answer.push(temp)
        }
        if (lion > apeach && lion - apeach > max) {
            answer = [temp]
            max = lion - apeach
        }
    }
    if (max === -Infinity) {
      return [-1]  
    }
  	// (3) 최대가 되는 경우가 여러 개인 경우 정렬을 통해 가장 낮은 점수를 많이 맞힌 경우의 수를 배열의 맨 앞으로 가져온다.
    const sorted = answer.map(v => v.join("")).sort((a,b) => {
        for (let i = 10; i >= 0; i--) {
            if (a[i] === b[i]) {
                continue
            }
            return b[i] - a[i]
        }
    })
    return sorted[0].split("").map(Number)
}

출처: 프로그래머스 - 양궁대회 https://school.programmers.co.kr/learn/courses/30/lessons/92342#