[DFS, 백트래킹, 조합] 프로그래머스 lv.2 양궁 대회

프로그래머스 lv.2 양궁 대회

문제 바로가기

문제 요약

• 어피치가 양궁을 먼저 다 쐈다. 화살의 수와 어피치의 과녘 현황을 입력값으로 줬을 때, 라이언이 어떻게 과녘을 맞춰야 최대 점수차이로 이길 수 있는지 반환해라.

주의할 점

• 최대 점수 차이가 같을 경우, 낮은 점수에 많이 맞은 경우를 답으로 처리한다.
• 배열에 해당하는 과녘은 10점 과녘부터 0점까지 순서대로 주어진다.

문제 접근

완전 탐색에 조기종료 조건이 가능하므로 DFS를 사용한 백트래킹
과녘의 수가 고정되어 있기 때문에 점수 현황을 고정 길이의 배열로 만들어서 과녘의 선택/ 미선택 두개의 정보를 담을 수 있다.

조기 종료 조건 (유망함수)

1. 남은 화살이 더이상 없을 때.
2. 과녘의 끝에 다다랐을 때.

오답노트

1. recursive overflow 에러 발생.
- DFS 접근이 틀렸나? 문제 전체 설계를 다시해야하나? 라는 패닉에 빠져있었는데, dfs 입력 형식을 배열로 만드는 오탈자 때문에 DFS를 종료시키지 못해 생긴 에러였다.
- 화살의 수를 1로 극단적으로 줄여서 실행했는데도 overflow가 떠서 찾을 수 있었다.

2. 조기종료 조건에 return문 누락
- 위 내용 디버깅 중에 조기 종료 조건을 수정하다가 return을 제거해버려서 한번 더 recursive 에러 발생했었다.

 

결론

• DFS 쓸 때는 함수 입출력 형식 주의하기
• 전역 변수 사용시 원복 확인하기
• 조기종료 return 문 누락 확인

기타 느낀 점

• arrows 를 전역으로 두고 사용했는데, 나는 메모리 차지는 많이하더라도 인자로 추가해서 결과값으로 사용하는 걸 선호한다.
• 전역 배열 수정하고 복구할 때 휴먼에러로 놓치기가 너무 쉽기 때문이다.

---

다른 사람의 풀이

• DFS가 아니라 순열, 조합을 활용해서 푼 예시를 봤다. 파이썬이었으면 그렇게 접근했을 거 같은데 JavaScript에서는 순열 조합을 아무래도 기피하게 되는 것 같다. JavaScript로 순열 조합 구현을 어떻게 하는지 예시 코드를 작성해보고 이를 활용했을 때 문제 풀이를 수도 코드로 작성해보겠다.
• 순열(permutation)은 순서가 다른 배열은 다른 경우의 수로 취급하고, 조합(combination)은 순서가 달라도 같은 경우의 수로 취급한다.
• 중복 조합 구현 함수

// 출처 - 코딩테스트 합격자되기 자바스크립트편 
// n길이의 중복을 허용한 조합배열을 얻는 함수

function getCombinationsWithRepeatition(arr, n) {
  if (n === 1) return arr.map((v) => [v]);
  const result = [];
  arr.forEach((fixed, idx, arr) => {
    const rest = arr.slice(idx);
    const combis = getCombinationsWithRepeatition(rest, n - 1);
    const combine = combis.map((v) => [fixed, ...v]);
    result.push(...combine);
  });
  return result;
} 
// 결과 배열의 길이는 (중복을 제거한) arr의 길이 + ( (long!) / (long-n) ) / n!, 결국 11! 쯤 됨

중복순열을 활용한다면, 우선 라이언이 쏘는 모든 경우의 화살에 대한 배열을 구할 수 있다.
결과값 = getCombinationsWithRepeatition([0부터 10까지의 과녘점수], 화살의 개수)
이 조합 결과값을 활용해 반복문을 돌면서 라이언의 점수를 계산해서 객체에 담고, 최대 차이인 경우 답을 갱신해주는 식으로 구현할 수 있다.
책에서 구현한 방식인데, 백트래킹을 이용했다고 보기는 어려운 거 같다. 그리고 조합 전체를 돌지 않는 방법이 있는지 고민해볼 필요가 있는 것 같다.

---

제출 코드 (DFS, 백트래킹)

function solution(N, counters_info) {
  // [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

  counters_info = counters_info.reverse(); // reverse를 통해 인덱스가 점수가 되도록 처리
  const answer = [];
  let arrows = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  let max_score = -1;

  dfs(0, N);

  // 종료 조건
  // 1. 남은 화살이 0개 일 때,
  // 2. 과녘 번호가 11 이상일 때

  // 라이언의 화살 현황
  function dfs(score_idx, arrow_res) {
    if (arrow_res < 1 || score_idx > 10) {
      let result = getDiffScore(arrows);
      if (result > max_score) {
        arrows[0] += arrow_res;
        answer.push([...arrows]);
        arrows[0] -= arrow_res;
        max_score = result;
      }
      return;
    }

    let need_arrow_cnt = counters_info[score_idx] + 1;
    let temp = arrows[score_idx];
    if (arrow_res >= need_arrow_cnt) {
      arrows[score_idx] = need_arrow_cnt;
      dfs(score_idx + 1, arrow_res - need_arrow_cnt);
    }
    arrows[score_idx] = temp;
    dfs(score_idx + 1, arrow_res);
  }

  function getDiffScore(ryan) {
    let rs = 0;
    let as = 0;
    for (let i = 0; i < 11; i++) {
      if (ryan[i] > counters_info[i]) {
        rs += i;
      } else if (ryan[i] === counters_info[i]) {
        continue;
      } else {
        as += i;
      }
    }
    const score_diff = rs - as;
    return score_diff > 0 ? score_diff : -1;
  }

  // 필요한 점수, 필요한 화살
  // 필요한 점수, 갖고 있는 화살

  // for문 돌면서 점수 계산

  let final = [-1];
  for (let ans of answer) {
    let result = getDiffScore(ans);
    if (result >= max_score && result != -1) {
      max_score = result;
      final = [...ans.reverse()];
    }
  }

  return final;
}