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

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

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

2022 KAKAO BLIND RECRUITMENT

LEVEL 2

문제설명

라이언과 어피치가 양궁 결승 경기를 치른다. 경기 규칙은 다음과 같다.

• 어피치가 n발을 쏜 후 라이언이 n발을 쏜다.
• 만약 k(1~10 사이의 자연수)점을 어피치가 a발 맞혔고, 라이언이 b발 맞혔다면 a < b일 때 라이언 k점을, a >= b 일 때 어피치가 k점을 가져간다. 만약 a, b가 둘 다 0이라면 아무도 k점을 가져가지 않는다.
• 모든 과녁 점수에 대해 각 선수의 최종 점수를 계산하여 최종 점수가 더 큰 쪽이 우승자가 된다. 하지만 둘이 동점이라면 어피치가 우승하게 된다.

현재 어피치가 n발을 다 쏘고 라이언이 화살을 쏠 차례다. 라이언이 어피치를 상대로 가장 큰 점수차로 이기기 위해서는 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지 구하는 solution 함수를 작성하시오. 가장 큰 점수차로 이기는 경우가 여러 가지일 경우 가장 낮은 점수를 더 많이 맞힌 경우를 return 하시오. (만약 라이언이 우승할 수 있는 경우가 없다면 [-1]을 return)

INPUT

n

• 라이언이 쏠 화살의 개수
• 1 ≤ n ≤ 10

info

• 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열
• info의 길이 = 11
• info의 원소 총합 = n

OUTPUT

• 가장 큰 점수차로 라이언이 이기기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지 담은 정수 배열
• 배열의 길이는 11
• 배열의 i번째 원소는 과녁의 (10 - i)점을 맞힌 화살의 개수
• 만약 라이언이 우승할 수 있는 경우가 없다면 [-1]

나의 풀이

DFS로 라이언이 n발의 화살로 만들 수 있는 점수판을 탐색하며 maxDiff와 result를 갱신한다.

1. 가장 큰 점수차를 담을 maxDiff를 선언, 초깃값은 0 / 가장 큰 점수차를 만드는 라이언의 점수판을 담을 배열 result를 선언, 초깃값은 빈배열
2. 재귀함수 dfs 선언
   • Parameters : 어피치의 누적점수를 담은 apeachScore, 라이언의 누적점수를 담은 ryanScore, 현재까지 라이언이 쏜 화살 개수를 담은 cnt, 현재 어느 과녁 점수를 살펴볼 것인지를 담은 idx (idx = 10 - 과녁 점수), 현재 라이언의 점수판을 담은 ryanInfo
   • 현재까지 라이언이 쏜 화살의 개수가 n보다 크면 탐색 중지 (cut > n일때 return)
   • 10점부터 0점까지 점수 계산이 모두 끝나면 점수차를 구해 maxDiff보다 큰지 비교 후 탐색 중지
     • 만약 현재 점수차가 maxDiff보다 크다면 해당 점수차로 maxDiff를 갱신하고 result를 ryanInfo로 갱신
     • 만약 현재 점수차가 maxDiff와 같다면 result에 ryanInfo를 추가
   • Case 1 : 라이언이 득점
     • 아직 남은 화살이 있을 때 (n > cnt)
   • Case 2 : 어피치가 득점
     • 라이언이 해당 과녁 점수에 화살을 쏘지 않고, 어피치가 해당 과녁 점수에 1개 이상의 화살을 맞혔을 때 ( info[idx] > 0)
   • Case 3 : 아무도 득점하지 못함
     • 라이언이 해당 과녁 점수에 화살을 쏘지 않고, 어피치가 해당 과녁 점수에 맞힌 화살이 없을 때 (info[idx] === 0)
3. dfs 함수 호출
   • Arguments : apeachScore = 0, ryanScore = 0, cat = 0, idx = 0, ryanInfo = new Array(11).fill(0)
4. result에 담긴 점수판이 1개 이상일 때, 가장 낮은 점수를 더 많이 맞힌 경우가 앞으로 오도록 result를 정렬
   • ! 처음 시도에서 테스트케이스 8, 18번이 통과되지 않았는데, 가능한 경우가 여러 가지일 경우 가장 낮은 점수를 더 많이 맞힌 경우가 return 되도록 구현되지 않아서였다. 해당 부분을 추가하니 모든 테스트케이스를 통과할 수 있었다.
5. 라이언이 이길 수 있는 경우 (maxDiff > 0) result[0]을, 이길 수 없는 경우 [-1]을 return

function solution(n, info) {
  // 1-1. 가장 큰 점수차를 담을 maxDiff 선언
  let maxDiff = 0;
  // 1-2. 가장 큰 점수차를 만드는 라이언의 점수판을 담을 배열 result를 선언
  let result = [];
  // 2. 재귀함수 dfs 선언
  function dfs(apeachScore, ryanScore, cnt, idx, ryanInfo) {
    // 2-1. 현재까지 라이언이 쏜 화살의 개수가 n보다 크면 탐색 중지
    if (cnt > n) return;
    // 2-2. 10점부터 0점까지 점수계산이 모두 끝난 경우 탐색 중지
    if (idx > 10) {
      const diff = ryanScore - apeachScore;
      // 2-2-1. 현재 점수차가 maxDiff보다 큰 경우
      if (diff > maxDiff) {
        maxDiff = diff; // maxDiff를 diff로 갱신
        ryanInfo[10] = n - cnt; // 남은 화살로 모두 0점 과녁을 맞힘
        result = [ryanInfo]; // result를 ryanInfo로 갱신
      }
      // 2-2-2. 현재 점수차가 maxDiff와 같은 경우
      if (diff === maxDiff) {
        ryanInfo[10] = n - cnt; // 남은 화살로 모두 0점 과녁을 맞힘
        result.push(ryanInfo); // result에 ryanInfo 추가
      }
      return;
    }
    // 2-3. Case 1 : 라이언이 득점
    if (n > cnt) {
      const newRyanScore = ryanScore + (10 - idx);
      const newRyanInfo = [...ryanInfo];
      newRyanInfo[idx] = info[idx] + 1; // 어피치보다 해당 과녁 점수를 1발 더 맞힘
      const newCnt = cnt + info[idx] + 1;
      dfs(apeachScore, newRyanScore, newCnt, idx + 1, newRyanInfo);
    }
    // 2-4. Case 2 : 어피치가 득점
    if (info[idx] > 0) {
      const newApeachScore = apeachScore + (10 - idx);
      dfs(newApeachScore, ryanScore, cnt, idx + 1, ryanInfo);
    }
    // 2-5. Case 3 : 아무도 득점하지 못함
    if (info[idx] === 0) {
      dfs(apeachScore, ryanScore, cnt, idx + 1, ryanInfo);
    }
  }
  // 3. dfs 함수 호출
  dfs(0, 0, 0, 0, new Array(11).fill(0));
  // 4. result에 담긴 점수판이 1개 이상일 때,
  //    가장 낮은 점수를 더 많이 맞힌 경우가 앞으로 오도록 result를 정렬
  if (result.length > 1) {
    result.sort((a, b) => {
      for (let i = 10; i >= 0; i--) {
        if (a[i] !== b[i]) return b[i] - a[i];
      }
      return 0;
    })
  }
  // 5. 라이언이 이길 수 있는 경우 result[0]을, 이길 수 없는 경우 [-1]을 return
  return (maxDiff > 0) ? result[0] : [-1];
}