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

문제 개요

카카오배 양궁대회 결승전에서 라이언이 어피치를 가장 큰 점수 차이로 이기기 위한 화살 배분을 구하는 문제입니다.

핵심 규칙

• 어피치가 먼저 n발을 쏜 후 라이언이 n발을 쏜다
• 각 점수대에서 더 많은 화살을 맞힌 선수가 해당 점수를 가져간다
• 동점일 경우 어피치가 점수를 가져간다
• 둘 다 0발일 경우 아무도 점수를 가져가지 않는다
• 최종 점수가 같을 경우 어피치가 우승한다

우선순위 규칙

같은 점수 차이로 이기는 방법이 여러 개일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 선택해야 합니다.

접근 방법

1단계: 문제 분석

먼저 문제의 핵심을 파악했습니다:

• 라이언이 이겨야 한다 (라이언 점수 > 어피치 점수)
• 가장 큰 점수 차이로 이겨야 한다
• 같은 점수 차이일 때는 낮은 점수부터 비교한다

2단계: 점수 계산 로직 구현

function calculateScore(myArrows) {
  let myScore = 0;
  let opponentScore = 0;

  for (let i = 0; i < 11; i++) {
    const pointValue = 10 - i;
    const myArrowCount = myArrows[i];
    const opponentArrowCount = info[i];

    if (myArrowCount > opponentArrowCount) {
      myScore += pointValue;
    } else if (opponentArrowCount > myArrowCount) {
      opponentScore += pointValue;
    } else if (myArrowCount === opponentArrowCount && myArrowCount > 0) {
      // 동점일 때는 어피치가 점수를 가져감
      opponentScore += pointValue;
    }
    // 둘 다 0발일 때는 아무도 점수를 가져가지 않음
  }

  return { myScore, opponentScore, scoreDiff: myScore - opponentScore };
}

3단계: 우선순위 비교 함수

문제에서 요구하는 우선순위 규칙을 구현했습니다:

function isBetterResult(newResult, currentBest) {
  for (let i = 10; i >= 0; i--) {
    if (newResult[i] > currentBest[i]) {
      return true;
    } else if (newResult[i] < currentBest[i]) {
      return false;
    }
  }
  return false;
}

여기서 i = 10부터 시작하는 이유는 배열 인덱스가 0점(인덱스 10)부터 시작하기 때문입니다.

4단계: 백트래킹 알고리즘

모든 가능한 화살 배분을 탐색하는 백트래킹을 구현했습니다:

function dfs(scoreIndex, remainingArrows, currentResult) {
  if (scoreIndex === 11) {
    if (remainingArrows === 0) {
      const { myScore, opponentScore, scoreDiff } =
        calculateScore(currentResult);

      if (myScore > opponentScore) {
        if (scoreDiff > maxScoreDiff) {
          maxScoreDiff = scoreDiff;
          bestResult = [...currentResult];
        } else if (scoreDiff === maxScoreDiff) {
          if (isBetterResult(currentResult, bestResult)) {
            bestResult = [...currentResult];
          }
        }
      }
    }
    return;
  }

  for (let arrows = 0; arrows <= remainingArrows; arrows++) {
    currentResult[scoreIndex] = arrows;
    dfs(scoreIndex + 1, remainingArrows - arrows, currentResult);
  }
}

핵심 구현 포인트

1. 점수 차이 기반 최적화

처음에는 단순히 라이언의 점수만 비교했는데, 문제를 다시 읽어보니 가장 큰 점수 차이로 이기는 것이 목표였습니다. 이를 위해 scoreDiff를 도입했습니다.

2. 우선순위 규칙의 정확한 구현

문제의 예시를 보면:

• [2,3,1,0,0,0,0,1,3,0,0] vs [2,1,0,2,0,0,0,2,3,0,0]
• [2,1,0,2,0,0,0,2,3,0,0]를 선택해야 함

이는 0점부터 순서대로 비교해서 더 많은 화살을 맞힌 경우를 선택하는 것입니다.

3. 엣지 케이스 처리

• n=0인 경우: [-1] 반환
• 이길 수 없는 경우: [-1] 반환
• 동점인 경우: 어피치가 점수를 가져감
• 둘 다 0발인 경우: 아무도 점수를 가져가지 않음

최종 코드

function solution(n, info) {
  if (n === 0) {
    return [-1];
  }

  let maxScoreDiff = -1;
  let bestResult = [-1];

  function calculateScore(myArrows) {
    let myScore = 0;
    let opponentScore = 0;

    for (let i = 0; i < 11; i++) {
      const pointValue = 10 - i;
      const myArrowCount = myArrows[i];
      const opponentArrowCount = info[i];

      if (myArrowCount > opponentArrowCount) {
        myScore += pointValue;
      } else if (opponentArrowCount > myArrowCount) {
        opponentScore += pointValue;
      } else if (myArrowCount === opponentArrowCount && myArrowCount > 0) {
        opponentScore += pointValue;
      }
    }

    return { myScore, opponentScore, scoreDiff: myScore - opponentScore };
  }

  function isBetterResult(newResult, currentBest) {
    for (let i = 10; i >= 0; i--) {
      if (newResult[i] > currentBest[i]) {
        return true;
      } else if (newResult[i] < currentBest[i]) {
        return false;
      }
    }
    return false;
  }

  function dfs(scoreIndex, remainingArrows, currentResult) {
    if (scoreIndex === 11) {
      if (remainingArrows === 0) {
        const { myScore, opponentScore, scoreDiff } =
          calculateScore(currentResult);

        if (myScore > opponentScore) {
          if (scoreDiff > maxScoreDiff) {
            maxScoreDiff = scoreDiff;
            bestResult = [...currentResult];
          } else if (scoreDiff === maxScoreDiff) {
            if (isBetterResult(currentResult, bestResult)) {
              bestResult = [...currentResult];
            }
          }
        }
      }
      return;
    }

    for (let arrows = 0; arrows <= remainingArrows; arrows++) {
      currentResult[scoreIndex] = arrows;
      dfs(scoreIndex + 1, remainingArrows - arrows, currentResult);
    }
  }

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

  return bestResult;
}

테스트 결과

입출력 예시들이 모두 정확히 일치합니다:

• 예시 1: n=5, info=[2,1,1,1,0,0,0,0,0,0,0] → [0,2,2,0,1,0,0,0,0,0,0]
• 예시 2: n=1, info=[1,0,0,0,0,0,0,0,0,0,0] → [-1]
• 예시 3: n=9, info=[0,0,1,2,0,1,1,1,1,1,1] → [1,1,2,0,1,2,2,0,0,0,0]
• 예시 4: n=10, info=[0,0,0,0,0,0,0,0,3,4,3] → [1,1,1,1,1,1,1,1,0,0,2]

시간복잡도

• 최악의 경우: O(n^11)
• 실제로는 백트래킹의 가지치기로 인해 훨씬 효율적
• n의 최대값이 10이므로 충분히 빠름