[프로그래머스] 양궁대회 - 자바스크립트

문제

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

카카오 기출문제이다.
문제도 상당히 길고 Test case 8, 18이 쉽지 않았던 문제라 level2에서도 상당한 난이도로 느껴진다.

---

코드

function solution(n, info) {
  let answer = new Array(11).fill(0);
  let answerDiff = Number.MIN_SAFE_INTEGER;

  function isSmallScoreArr(scoreArr) {
    for (let i = 10; i >= 0; i--) {
      if (scoreArr[i] > answer[i]) return true;
      else if (scoreArr[i] < answer[i]) return false;
    }
  }

  function dfs(L, idx, ryanInfo) {
    if (idx === 10 && L < n) {
      ryanInfo[10] = n - L;
      L = n;
    }

    if (L === n) {
      let appeachScore = 0;
      let ryanScore = 0;

      ryanInfo.forEach((elem, i) => {
        if (!elem && !info[i]) return;

        const score = 10 - i;
        if (info[i] - elem >= 0) appeachScore += score;
        else if (info[i] - elem < 0) ryanScore += score;
      });

      const diff = ryanScore - appeachScore;

      if (answerDiff < diff) {
        answerDiff = diff;
        answer = ryanInfo;
      } else if (answerDiff === diff) {
        if (isSmallScoreArr(ryanInfo)) answer = ryanInfo;
      }
      return;
    }

    const appeachArrowLength = info[idx];

    if (n - L >= appeachArrowLength + 1) {
      ryanInfo[idx] = appeachArrowLength + 1;
      dfs(L + appeachArrowLength + 1, idx + 1, [...ryanInfo]);
      ryanInfo[idx] = 0;
    }
    dfs(L, idx + 1, [...ryanInfo]);
  }

  dfs(0, 0, new Array(11).fill(0));

  if (answerDiff <= 0) return [-1];
  return answer;
}

---

풀이

출처 : 프로그래머스

문제의 조건

 

라이언, 어피치가 총 n발의 화살을 쏜다.
화살이 맞춘 기록은 배열 0~10 인덱스에 기록되고, 0번 인덱스부터 10점, 10번 인덱스는 0점이다.

 

라이언이 전년도 우승자라, 불리함이 있다.
라이언은 어피치보다 많은 화살을 명중시켜야 해당 인덱스 점수를 가져간다.
반면 맞춘 화살 수가 어피치 >= 라이언 이라면 어피치가 점수를 가져간다.

 

예를 들면 0번 인덱스에 대해 라이언=2, 어피치=1이면 라이언이 10점을 가져간다.

예를 들면 0번 인덱스에 대해 라이언=1, 어피치=1이면 어피치가 10점을 가져간다.

둘 다 쏘지 않은 점수에 대해서는, 아무도 가져가지 않는다.

 

주어진 배열 info는 어피치가 맞춘 화살의 인덱스 정보다.

라이언은 얻은 점수의 총합이 어피치보다 많아야만 우승할 수 있다.

 

여기서, 모든 경우에 대해 어피치의 총 점수 >= 라이언의 총 점수라면 어피치가 우승하고 [-1]을 반환한다.

 

우리는 라이언이 어피치를 가장 큰 점수차로 누르고 우승할 때의 라이언의 화살 정보를 반환해야 한다.
이 때 라이언이 가장 큰 점수 차이로 우승하는 방법이 여러 가지라면, 가장 낮은 점수를 더 많이 맞힌 경우를 반환한다.

• 이 정보를 해결하지 않으면 테스트케이스 8, 18번에서 실패하게 된다.

 

주어진 범위

1 <= n <= 10
info.length = 11
info의 i번째 원소 = 10-i 점을 맞춘 갯수
라이언은 n발의 화살을 다 쏴야 한다.

 

풀이 방향

배열이 11개, n이 최대 10개이므로 완전탐색을 수행하면 된다.

n과 배열 인덱스를 기반으로 하는 dfs로 풀이할 계획이다.

 

우선, dfs로 화살을 하나씩 쏴도 된다.
그러나 특정 인덱스에 어피치보다 많은 화살을 쏴서 점수를 탈취할 것인지, 아니면 아예 안쏠 것인지를 따지는게 더 낫겠다.

 

그리하여 기본적으로 현재 인덱스 idx에서 다음과 같은 경우가 있다.

1. 라이언이 어피치보다 많은 화살을 쏜다.
2. 라이언이 화살을 쏘지 않고 넘어간다.

이 두 경우를 가지고 dfs를 수행해본다.

 

여기서, 10번 인덱스를 판단할 때를 주의해야 한다.
"라이언은 모든 화살을 쏴야 하기 때문에" 만약 10번 인덱스를 판단할 때, 화살이 남아있다면 모두 쏴버리자.

 

이제 정답 처리를 할 때는 다음의 과정을 따른다.

 

각 인덱스 별로 (어피치 화살 갯수 - 라이언 화살 갯수) 값을 구한다.
해당 값이 0보다 크거나 같다면 어피치의 점수이며, 0보다 작다면 라이언의 값이다.
어피치와 라이언이 모두 화살을 쏘지 않아도, 0-0=0으로 어피치의 점수가 될 수 있다. 이것을 제외한다.

 

구한 어피치의 최종 점수와 라이언 최종 점수차이를 구한다.

기록해둔 가장 큰 차이보다 방금 구한 점수차이가 크다면 정답 후보(=라이언이 쏜 화살의 배열)를 갱신한다.

점수차이가 같다면 추가적으로 가장 낮은 점수를 더 많이 맞힌 경우를 판단해야 한다.

 

정답 후보 배열에 있는 기존 배열과, 현재 라이언이 쏜 화살의 배열 비교한다.
이때는 각 배열의 맨 마지막 원소부터 탐색하면서, 원소가 큰 인덱스를 먼저 가진 배열이 정답 후보 배열이 된다.

 

마지막으로 위의 설명들을 반영한 주석을 추가한 코드를 첨부하였다.

---

주석을 첨부한 코드

function solution(n, info) { 
  let answer = new Array(11).fill(0); // 정답 후보 배열
  let answerDiff = Number.MIN_SAFE_INTEGER; // 라이언의 총 점수 - 어피치의 총 점수

  function isSmallScoreArr(scoreArr) {
    for (let i = 10; i >= 0; i--) {
      if (scoreArr[i] > answer[i]) return true;
      else if (scoreArr[i] < answer[i]) return false;
    }
  } // 정답 후보 배열을 구하기 위해 인덱스 마지막을 비교하는 함수

  function dfs(L, idx, ryanInfo) {
    if (idx === 10 && L < n) {
      ryanInfo[10] = n - L;
      L = n;
    } // 판단할 인덱스가 10이면 남은 화살을 모두 소진하면서, L값을 갱신한다.

    if (L === n) {
      let appeachScore = 0;
      let ryanScore = 0;

      ryanInfo.forEach((elem, i) => {
        if (!elem && !info[i]) return;

        const score = 10 - i;
        if (info[i] - elem >= 0) appeachScore += score;
        else if (info[i] - elem < 0) ryanScore += score;
      }); // 라이언, 어피치의 총 점수을 구한다.

      const diff = ryanScore - appeachScore;

      if (answerDiff < diff) {
        answerDiff = diff;
        answer = ryanInfo; 
      } else if (answerDiff === diff) {
        if (isSmallScoreArr(ryanInfo)) answer = ryanInfo;
      } // 차이가 더 커졌다면 바로 정답후보배열을 갱신하고, 차이가 같다면 더 작은 점수를 많이 쏜 경우를 정답후보로 갱신한다.
      return;
    }

    const appeachArrowLength = info[idx]; // 인덱스에 현재 어피치가 쏜 화살의 갯수.

    if (n - L >= appeachArrowLength + 1) {
      ryanInfo[idx] = appeachArrowLength + 1;
      dfs(L + appeachArrowLength + 1, idx + 1, [...ryanInfo]);
      ryanInfo[idx] = 0;
    } // 어피치가 화살을 쏜 것 보다 1개 더 많은 화살을 쏴서 점수를 뺏어온다.
    dfs(L, idx + 1, [...ryanInfo]); // 혹은 현재 인덱스의 점수를 포기한다.
  }

  dfs(0, 0, new Array(11).fill(0));

  if (answerDiff <= 0) return [-1]; // 차이가 0 이하라면 어피치의 승리이므로 [-1] 반환
  return answer;
}