[알고리즘/프로그래머스/카카오] 양궁대회(JS)

문제

---

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

프로그래머스

 

풀이

---

문제를 반복해 읽으면서 라이언이 화살을 (어피치 개수 + 1) 또는 0개의 화살을 쏠 수 있을 거라고 생각했다. 

이 경우, 화살을 쏘거나 쏘지 않거나의 2가지 경우^최대 레벨 = 10으로 1024가 최대 가지수이므로, DFS를 생각했지만 어려워서 이 블로그를 참고해 이해하였다. 

 

크게 보면, 

1. 화살을 쏠 때마다 현재 점수와 정답 배열(점수 당 사용한 라이언의 화살 개수 배열)을 갱신하며 depth를 내려간다. 

2. 배열의 idx가 10인 경우(0점), 남은 화살을 모두 사용한다. 이는 가장 낮은 점수를 더 많이 맞힌 배열을 판단할 수 있도록 한다.

3. 화살을 모두 사용했다면, 라이언과 어피치의 점수를 구하고, return 한다.

    - 각 배열의 idx에서 (어피치 점수 - 라이언 점수) >= 0이면 어피치의 승리, 이외의 경우 라이언의 승리로 판단한다.

    - 점수 차이 이전 정답보다 더 크다면 갱신하고, 점수 차이가 이전 정답과 동일하다면 낮은 점수를 더 많이 맞힌 배열인지 확인해 갱신한다.

4. (어피치 개수 + 1)개의 화살이 남아있다면, 해당 점수에 (어피치 개수 + 1)개의 화살을 사용하거나 / 사용하지 않거나 두 가지 경우를 DFS로 완전탐색한다. 

5. 마지막으로, 점수 차이가 0이하이면 어피치가 승리한 것이므로 [-1]을, 아닌 경우 정답 배열 ryanInfo를 반환한다. 

function solution(n, info) {
  let answer = new Array(11).fill(0); 
  let maxDiff = Number.MIN_SAFE_INTEGER; // 최대 라이언-어피치 점수 차이

  // 인덱스 마지막에 값이 먼저 있는 배열 판단
  function isSmallerScoreArr(scoreArr) {
    for (let i = 10; i >= 0; i--) {
      if (scoreArr[i] === answer[i]) continue;
      else if (scoreArr[i] > answer[i]) return true; 
      else return false;
    }
  }

  // DFS(사용한 화살 개수, 현재 점수, 라이언 점수 당 사용한 화살 개수)
  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;

      for (let i = 0; i < ryanInfo.length; i++) {
        const aScore = info[i];
        const rScore = ryanInfo[i];
        const score = 10 - i;

        if (!rScore && !aScore) continue;

        if (aScore - rScore >= 0) appeachScore += score;
        else ryanScore += score;
      }

      const diff = ryanScore - appeachScore;

      if (maxDiff < diff) {
        // 차이가 더 크면 갱신하고,
        maxDiff = diff;
        answer = ryanInfo;
      } else if (maxDiff === diff) {
        // 같으면 가장 작은 점수를 많이 쓴 배열인 경우 정답 배열 갱신
        if (isSmallerScoreArr(ryanInfo)) answer = ryanInfo;
      }

      return;
    }

    const appeachCnt = info[idx]; // 어피치가 현재 쏜 화살 개수

    // 현재 점수 획득
    if (n - L >= appeachCnt + 1) {
      ryanInfo[idx] = appeachCnt + 1;
      DFS(L + appeachCnt + 1, idx + 1, [...ryanInfo]);
      ryanInfo[idx] = 0; // 돌아나올 때 점수 초기화
    }

    // 현재 점수 포기
    DFS(L, idx + 1, [...ryanInfo]);
  }

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

  // 차이가 0 이하면 어피치의 승리 
  if (maxDiff <= 0) return [-1];
  return answer;
}

 

다음에 다시 한 번 풀어봐야겠다. 

 

 

REF
https://inpa.tistory.com/entry/JS-%F0%9F%93%9A-forEach%EC%97%90-break%EA%B1%B0%EB%8A%94-%EB%B0%A9%EB%B2%95