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

문제

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

문제 정의

라이언과 어피치가 양궁대결을 한다.
배점은 과녁의 가장 가운데부터 10점, 9점, 8점, ..., 1점, 과녁 밖으로 나갈 경우 0점이다.
어피치가 한 점수를 n발 맞혔을때, 라이언이 같은 점수를 n발 이하로 맞추면 어피치가 점수를 얻는다. 따라서 라이언이 점수를 얻기 위해선 같은 점수를 n+1발 이상 맞혀야 한다.

화살이 n발 주어지고, 어피치가 과녁에 몇 발 맞혔는지 주어졌을 때, 라이언이 가장 큰 점수차로 이기려면 몇점에 몇발씩 맞혀야 하는지를 출력해야 한다.

예외사항

• 만약 가장 큰 점수차를 만들수 있는 경우가 여러개라면, 가장 낮은 점수를 많이 맞힌 경우를 출력한다.
• 라이언과 어피치의 최종 점수가 같을 경우 어피치가 승리한다.

해결 방안

info의 길이가 11이니 모든 조합을 확인하는 방법 즉, 완전탐색으로 풀 수 있을 것 같았다.

우리가 찾아야 하는건 라이언이 이기는 경우다.
라이언이 이기기 위해선 어피치보다 점수를 많이 얻어야 한다.
어피치보다 많은 점수를 얻기 위해선 어피치가 맞힌 과녁에 화살을 더 많이 맞혀서 어피치의 점수를 라이언이 뺏어올 수 있게 하는 방법이 있다.
즉, 어피치가 n발을 맞혔다면 라이언이 n+1발 맞히면 해당 점수를 뺏어올 수 있다.

이를 통해 조합을 함수로 아래와 같이 러프하게 구현해볼 수 있다.

combination(0, Array(11).fill(0), n);

function combination(cur, ryanInfo, arrows) {
    for (let i = cur; i <= 10; i++) {
      ryanInfo[i] += info[i] + 1;
      arrows -= info[i] + 1;
      combination(i + 1, ryanInfo, arrows);
      ryanInfo[i] -= info[i] + 1;
      arrows += info[i] + 1;
  }

ryanInfo는 라이언이 맞힌 과녁의 점수를 기록하는 배열이고, arrows는 남은 화살의 수다.

ryanInfo[i]에 info[i]+1을 더해줌으로써, 어피치보다 10-i점 과녁에 한 발 많이 맞힌것이 된다.

그리고 남은 화살의 수를 그만큼 빼주고 (arrows -= info[i] + 1), 재귀를 돈다.(combination(i + 1, ryanInfo, arrows))

그리고 재귀를 탈출했을 때는 다시 값을 돌려놓는다.

ryanInfo[i] -= info[i] + 1;
arrows += info[i] + 1;

이제 재귀의 종료조건을 만들어줘야 한다.
화살이 0개 이하라면 더 이상 사용할 화살이 없는 것이므로 종료를 시켜준다.

하지만 여기서 남은 화살이 0개 미만일때랑, 정확히 0개 일때를 분리해줘야 한다. 왜냐하면 정확히 0개 일때는 화살을 정해진 수량만큼 딱 맞게 사용한 것이지만 화살이 0개 미만일 경우에는 정해진 수량보다 더 사용한 것이기 때문이다.

function combination(cur, ryanInfo, arrows) {
  if(arrows < 0) return;
  if(arrows === 0) {
	// 추가 작업
	return;
  }
  for (let i = cur; i <= 10; i++) {
    ...
  }
}

남은 화살(arrows)가 0개일 때는 ryanInfo와 info를 이용해서 어피치와 라이언의 점수를 계산해준다.
그리고 둘의 점수차를 구한 뒤, 점수차가 이전에 저장해 둔 최대 점수차보다 클 경우 점수차를 갱신하고 답도 갱신해준다.

function combination(cur, ryanInfo, arrows) {
  if(arrows < 0) return;
  if(arrows === 0) {
    
	...
    
    if (maxDiff < diff) {
      maxDiff = diff;
      answer = ryanInfo.map((e) => e);
    } 
	return;
  }
  
  for (let i = cur; i <= 10; i++) {
    ...
  }
}

만약 점수차가 이전 점수차와 동일할 경우에는 낮은 점수를 많이 맞힌 경우가 답이 된다.
따라서 점수차가 같을 경우도 따로 조건으로 걸어준다.

function combination(cur, ryanInfo, arrows) {
  if(arrows < 0) return;
  if(arrows === 0) {
    
	...
    
    if (maxDiff < diff) {
      ...
    }
    // 점수차가 같을 경우 낮은 점수에 많이 맞은 것을 답으로 한다.
    else if (maxDiff === diff) {
      for (let i = 10; i >= 0; i--) {
        if (ryanInfo[i] > answer[i]) {
          answer = ryanInfo.map((e) => e);
          break;
        } else if (answer[i] > ryanInfo[i]) break;
      }
   	}
	return;
  }
  
  for (let i = cur; i <= 10; i++) {
    ...
  }
}

만약 ryanInfo[i] += info[i]+1로 마지막 인덱스까지 전부 채웠는데, 화살이 남는 경우가 있을 수도 있다.
예를 들면 아래와 같은 경우 틀렸다고 나온다.

따라서 화살이 남는 경우에는 화살을 전부 가장 낮은 점수인 0점(ryanInfo[10])에 맞힌다. (점수차가 동일한 것중에는 가장 낮은 점수에 많이 맞은 것이 답이 되기 때문)

function combination(cur, ryanInfo, arrows) {
  if(cur < 11 && arrows < 0) return;
  if(cur === 11 || arrows === 0) {
    ryanInfo[10] += arrows;
	
    ...
    
   	if (maxDiff < diff) {
      maxDiff = diff;
      answer = ryanInfo.map((e) => e);
    }
    // 점수차가 같을 경우 낮은 점수에 많이 맞은 것을 답으로 한다.
    else if (maxDiff === diff) {
      for (let i = 10; i >= 0; i--) {
        if (ryanInfo[i] > answer[i]) {
          answer = ryanInfo.map((e) => e);
          break;
        } else if (answer[i] > ryanInfo[i]) break;
      }
   	}
    ryanInfo[10] -= arrows; 
	return;
  }
  
  for (let i = cur; i <= 10; i++) {
    ...
  }
}

cur === 11 일때로 조건을 걸어주는 이유는 ryanInfo[10] 까지 info[i]+1이 반영되어야 올바른 값이 나오기 때문이다.
하지만 만약 ryanInfo[10] += info[10]+1을 했을때, 화살을 초과해서 사용했다면 arrows가 음수가 될 것이다. 이는 ryanInfo[10] += arrows를 통해서 초과분만큼 ryanInfo[10]에서 빼준다.

info = [0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3]
ryanInfo = [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
arrows = 2

예를 들어 위와 같은 상태에서 아래 코드를 수행해주면

ryanInfo[10] += info[10] + 1;
arrows -= info[10] + 1;
combination(i + 1, ryanInfo, arrows);

상태는 아래와 같이 바뀐다.

info = [0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3]
ryanInfo = [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 4]
arrows = -2

이때 ryanInfo[10] += arrows이 수행되면서 초과된 화살을 빼주면서 아래와 같은 상태가 된다.

info = [0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3]
ryanInfo = [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2]
arrows = 0 // 실제로 arrows가 바뀌진 않는다.

또한 arrows가 음수가 됐을 때, 바로 return을 해주도록하는 조건문은 cur === 11 일때만 예외로 허용해주도록 바꿨다.

if(arrows < 0) return; // before
if(cur < 11 && arrows < 0) return; // after

마지막에 ryanInfo[10] -= arrows을 해주는 이유는, 재귀를 탈출했을 때도 ryanInfo는 동일한 배열이기 때문에 ryanInfo[10]에 arrows가 그대로 더해져있어서 오답이 나올수도 있기 때문이다.
따라서 마지막에 리턴하기 전에 다시 arrows로 빼주는 것이다.

후기

레벨 2 문제치곤 어려웠던 문제같다...