Programmers / Level 2 / 양궁대회 / JS

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

프로그래머스

 

문제 분석

이 문제는 고려할 것이 많기 때문에, 문제를 잘 읽어야 헷갈리지 않고 풀 수 있다.

• 더 많이 맞춘쪽이 해당 점수를 가져간다.
• 여러발 맞춰도 맞춘만큼 가져가는 것이 아닌, 해당 점수 한 번만 가져간다.
• 똑같이 맞췄다면 어피치가 해당 점수를 가져간다.
• '최대 점수'가 아닌, '최대 점수 차이'를 가지는 결과를 구해야 한다.
• '최대 점수 차이'를 가지는 방법이 여러개라면, 낮은 점수를 많이 맞춘 방법을 반환한다.

위에 보라색으로 된 것을 놓치거나, 헷갈릴 수 있으니 주의하면서 문제를 풀어야 한다.

 

풀이

function solution(n, info) {
  const apeachInfo = [...info];
  const lionInfo = Array.from({ length: 11 }, () => 0);
  let result = [-1];
  let maxDiff = -Infinity;

  function getTotalScore() {
    let apeachTotalScore = 0;
    let lionTotalScore = 0;

    for (let i = 0; i < 11; i++) {
      const curScore = 10 - i;

      if (lionInfo[i] > apeachInfo[i]) {
        lionTotalScore += curScore;
      } else if (apeachInfo[i] > 0) {
        apeachTotalScore += curScore;
      }
    }

    return { apeachTotalScore, lionTotalScore };
  }

  function isMoreLowerScore(arr1, arr2) {
    for (let i = 10; i >= 0; i--) {
      if (arr1[i] !== arr2[i]) {
        return arr1[i] > arr2[i];
      }
    }

    return false;
  }

  function dfs(scoreIndex, remainArrows, lionInfo) {
    if (scoreIndex === 11) {
      lionInfo[10] = remainArrows;

      const { apeachTotalScore, lionTotalScore } = getTotalScore();
      const diff = lionTotalScore - apeachTotalScore;

      if (
        diff > 0 &&
        (diff > maxDiff ||
          (diff === maxDiff && isMoreLowerScore(lionInfo, result)))
      ) {
        maxDiff = diff;
        result = [...lionInfo];
      }

      return;
    }

    // 현재 점수를 포기하는 경우
    dfs(scoreIndex + 1, remainArrows, lionInfo);

    // 현재 점수를 가져가는 경우
    const needArrows = apeachInfo[scoreIndex] + 1;

    // 남은 화살이 필요한 화살만큼 있을경우
    if (remainArrows >= needArrows) {
      lionInfo[scoreIndex] = needArrows;
      dfs(scoreIndex + 1, remainArrows - needArrows, lionInfo);
      lionInfo[scoreIndex] = 0;
    }
  }

  dfs(0, n, lionInfo);

  return result;
}

 

`getTotalScore()`

  function getTotalScore() {
    let apeachTotalScore = 0;
    let lionTotalScore = 0;

    for (let i = 0; i < 11; i++) {
      const curScore = 10 - i;

      if (lionInfo[i] > apeachInfo[i]) {
        lionTotalScore += curScore;
      } else if (apeachInfo[i] > 0) {
        apeachTotalScore += curScore;
      }
    }

    return { apeachTotalScore, lionTotalScore };
  }

어피치와 라이언의 총 점수를 구하는 함수이다.

만약 라이언이 어피치보다 더 많이 맞췄으면 라이언이 해당 점수를 가져간다.

그렇지 않고, 어피치가 라이언과 똑같이 맞췄거나 더 많이 맞췄을 경우에는 어피치가 점수를 가져간다.

둘다 0개로 맞추지 않았을 경우에는 둘다 점수를 얻지 않으므로,

else if에 0보다 클 때의 조건을 넣어주었다.

 

`isMoreLowerScore(arr1, arr2)`

  function isMoreLowerScore(arr1, arr2) {
    for (let i = 10; i >= 0; i--) {
      if (arr1[i] !== arr2[i]) {
        return arr1[i] > arr2[i];
      }
    }

    return false;
  }

"라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요."

라는 조건이 있다.

현재 배열은 10점, 9점, 8점, ... , 0점이 0, 1, 2, ... 10의 인덱스를 가지므로 역순으로 순회한다.

만약 arr1과 arr2가 과녁의 맞춘 화살의 개수가 다를 경우, arr1이 더 많이 맞췄다면 true를 반환한다.

모두 arr2가 더 많이 맞췄다면 false를 반환한다.

 

`dfs(scoreIndex, remainArrows, lionInfo)`

  function dfs(scoreIndex, remainArrows, lionInfo) {
    if (scoreIndex === 11) {
      lionInfo[10] = remainArrows;

      const { apeachTotalScore, lionTotalScore } = getTotalScore();
      const diff = lionTotalScore - apeachTotalScore;

      if (
        diff > 0 &&
        (diff > maxDiff ||
          (diff === maxDiff && isMoreLowerScore(lionInfo, result)))
      ) {
        maxDiff = diff;
        result = [...lionInfo];
      }

      return;
    }

    // 현재 점수를 포기하는 경우
    dfs(scoreIndex + 1, remainArrows, lionInfo);

    // 현재 점수를 가져가는 경우
    const needArrows = apeachInfo[scoreIndex] + 1;

    // 남은 화살이 필요한 화살만큼 있을경우
    if (remainArrows >= needArrows) {
      lionInfo[scoreIndex] = needArrows;
      dfs(scoreIndex + 1, remainArrows - needArrows, lionInfo);
      lionInfo[scoreIndex] = 0;
    }
  }

dfs로 풀이를 했다.

만약 배열 끝까지 도달했을 경우, 즉 scoreIndex가 11일 경우에 남은 화살을 전부 0점으로 설정해준다.

 

그리고 위에서 구현한 getTotalScore() 함수를 통해서 라이언과 어피치의 점수차를 구해준다.

점수차가 현재까지 구한 최대 점수차보다 크거나,

최대 점수차와 같지만 더 낮은 점수를 많이 맞춘 경우에는 답을 교체해준다.

 

그리고 다음 dfs로 넘어가는 경우에는 두 가지 경우가 있다.

현재 점수를 얻거나, 얻지 않는 경우.

현재 점수를 가져가지 않는 경우에는 단순히 인덱스만 하나 더해주고 다음 재귀로 넘어가면 된다.

현재 점수를 가져가는 경우에는 남은 화살이 어피치를 이기기 위해 필요한 화살만큼 있을 경우에는,

남아있는 화살에서 필요한 화살만큼 빼준 후에 다음 재귀로 넘어가면 된다.

물론 다음으로 넘어가는 재귀가 답이 아닐 수도 있기 때문에,

재귀가 끝나고 다시 돌아왔을 때는 0으로 다시 초기화해준다.