문제 요약

라이언과 어피치가 양궁대결을 합니다. 총 n발을 화살을 쏘게 되며 점수별로 더 많은 화살을 맞춘 사람이 점수를 가져가게 됩니다. 만약 동일한 개수를 명중시킨 경우 어피치가 점수를 가져갑니다. 최종적으로 높은 점수를 획득한 사람이 우승하게 됩니다.

예 : 10점과녁을 어피치가 2발, 라이언이 3발 -> 라이언이 10점 획득
예 : 10점과녁을 어피치가 3발, 라이언이 3발 -> 어피치가 10점 획득

어피치가 맞춘 과녁 점수의 개수가 담긴 배열(10점부터 0점 순서대로)을 매개변수로 주어집니다. 이때 라이언이 가장 큰 점수차로 우승하기 위한 n발의 화살을 어떤 과녁에 맞혀야 하는지를 반환하면 됩니다. 만약 라이언이 우승할 수 없는 경우에는 -1이 담긴 배열을 반환합니다.

나의 생각

화살을 가장 효율적으로 사용하기 위해서는 각 점수마다 어피치가 맞춘 개수보다 1개를 더 많이 맞춰서 점수를 획득하거나, 0발을 맞춰서 지는 경우를 생각하였습니다. 이를 구현하기 위해서 BFS를 사용하기로 결정하였습니다.

반복문안에서 처리해야하는 코드는 크게 두가지로 생각해볼 수 있습니다.

n발의 화살을 모둔 쏜 경우 스코어 계산
해당 점수에서 몇발의 화살을 쏠지 여부 적용
- 10 - 1점까지 모두 화살을 쏜 후 남은 화살은 전부 0점으로 간주하여 queue에 추가합니다.
- [그렇지 않은 경우 해당 점수에서] 0발을 쏘는 경우와, 어피치가 맞춘 개수 + 1 만큼 아직 쏘지 않은 화살이 남은 경우 queue에 추가합니다.

[CASE 23]을 통과하지 못한 경우 max가 0인 비긴 경우이기 때문에 조건을 추가해주어야 합니다.

function solution(n, info) {
    const queue = [[Array(11).fill(0), 0, 0]];
    let max = 0;
    let maxList = [-1];

    while (queue.length) {
        const [list, count, index] = queue.shift();

        if (count === n) {
            const score = info.reduce((acc, v, i) => {
                if (v > list[i]) {
                    acc -= 10 - i;
                } else if (v < list[i]) {
                    acc += 10 - i;
                }

                return acc;
            }, 0); 

            if (score > max) {
              max = score;
              maxList = list;
            } else if (score === max) {
              const isMax = [...list].sort((a, b) => b - a)
                .some((v, i) => maxList[i] < v);

              if (isMax) {
                maxList = list;
              }  
            }

            continue;
        }

        if (index === 10) {
          const newList = [...list];
          newList[index] = n - count;
          queue.push([newList, n, index + 1]);
        } else {
          queue.push([list, count, index + 1]);

          if (info[index] < n - count) {
            const newList = [...list];
            newList[index] = info[index] + 1;
            queue.push([newList, count + info[index] + 1, index + 1]); 
          }  
        }
    }

    if (max === 0) {
      return [-1];
    }

    return maxList;
}