프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

1. 입력과 출력

  • 입력
    • 화살 개수 N (N은 자연수, 1 ≤ N ≤ 10)
    • 어피치의 점수표 배열 info (고정 length : 11)
  • 출력
    • 라이언이 우승한다면, 라이언의 점수표 배열 (answer) 
      • 배열의 조건 확인하기!
        1. ( 1 ≤ 배열의 원소값 ≤ N) : 한 과녁에 0~N발 쏠 수 있다.
        2. ( ∑ 배열의 원소값 = N ) : 총 N발의 화살을 쏜다.
        3. 가장 큰 점수 차이로 우승할 경우의 점수표 배열을 반환해야 한다.
        4. 같은 점수 차이라면, 낮은 과녁(점수)을 더 많이 맞힌 경우의 점수표 배열을 반환해야 한다.
    • 라이언이 우승하지 못한다면, [-1] 반환

 

2. 문제 풀이 로직

다음과 같은 풀이 방법으로 DFS와 백트래킹 알고리즘을 사용하기로 생각하였다.

 

 

2-0. 초기값 설정하고, 헬퍼 함수 만들기

초기값은 마지막에 반환할 라이언의 점수표 배열인 answer와 가장 큰 점수 차이를 담을 maxDiff를 생성하였다.

만약 라이언이 이기지 못할 경우 answer을 수정하지않고 그대로 반환하도록 [-1]으로 저장하였다.

  // 0. 초기값 설정
  let answer = [-1] // 라이언의 점수표 배열
  let maxDiff = 0 // 라이언과 어피치의 점수 차이

 

 

 

isBetterDiff라는 헬퍼 함수는 문제의 조건 중 '낮은 과녁을 맞힌 경우의 배열을 반환'하기 위해 생성하였다.

 

저장되어있는 라이언의 점수표 배열인 answer를 받을 maxAnswer 인자와

DFS 탐색으로 얻은 라이언의 점수표 배열인 ryanArrows를 받을 currentAnswer 인자를 받는다.

 

두 개의 라이언 점수표를 받아서 currentAnswer의 점수표가 낮은 과녁을 많이 맞힌 경우인지 판단하여 그렇다면 true, 아니라면 false를 반환한다.

  // 1. isBetterDiff 함수 : 수정할 라이언의 점수표가 더 좋은 결과값인지 판단하는 함수
  //  ㄴ 낮은 과녁을 맞출수록 좋은 점수표
  function isBetterDiff(currentAnswer, maxAnswer) {
    for (let i = 10; i >= 0; i--) {
      if (currentAnswer[i] > maxAnswer[i]) return true
      if (currentAnswer[i] < maxAnswer[i]) return false
    }
    return false
  }

 

2-1. DFS 탐색 사용하기

본격적인 DFS 탐색에 앞서서 사용할 지역변수들에 대해 짚고 가보려고 한다.

 

- num : 과녁판 점수에 해당한다. (0점부터 시작하여 10점까지 탐색을 진행한다.)

- ryanArrow : 라이언이 현재까지 맞힌 화살의 개수를 담고 있는 점수표 배열이다. (info와 같이 고정 length는 11이다.)

- ryanScore : 라이언이 현재까지 얻은 점수이다. (초깃값 : 0점)

- apeachScroe : 어피치가 현재까지 얻은 점수이다. (초깃값 : 0점)

- leftArrow : 라이언이 쏠 수 있는 남은 화살의 개수이다. (초깃값 : N개)

 

 

위에서 살펴보았듯이 DFS 탐색을 할 경우는 크게 두 가지이다.

     ① 라이언이 점수를 얻는 경우 (어피치보다 1발 더 맞히는 경우)

     ② 라이언이 점수를 얻지 못하는 경우 (0발만 맞히는 경우)

 

각각의 경우 어떻게 탐색을 진행하는 지 더 자세히 알아보자.

 

① 라이언이 점수를 얻는 경우 (어피치보다 1발 더 맞히는 경우)

라이언이 점수를 얻을 수 있는지 먼저 확인한다.

(= leftArrow(남은 화살)이 Info[num](어피치 과녁판 점수)보다 많은 경우)

 

점수를 얻을 수 있는 경우라면, 라이언의 점수표 배열을 어피치보다 1발 더 맞히는 경우로 수정한다.

 

그리고 dfs 탐색과정을 재귀 호출한다.

이 때 다음 점수를 보기 위해 num + 1을 해주고, 라이언 점수를 득점해주고, 남은 화살 개수를 수정한 채로 호출한다.

 

라이언이 점수를 얻지 못하는 경우도 확인해야하기에 수정했던 라이언의 점수표 배열을 원상복구한다.

 

// 2. dfs 함수 : num(과녁판 점수), ryanArrows(라이언 점수표), ryanscore(라이언 점수), apeachScore(어피치 점수), leftArrow(남은 화살)
function dfs(num, ryanArrows, ryanScore, apeachScore, leftArrow) {
    // 분기 2. 라이언이 점수를 얻는 경우 -> 라이언의 점수를 더해줌
    if (leftArrow > info[num]) {
      ryanArrows[num] = info[num] + 1
      dfs(
        num + 1, // 다음 점수로 탐색 진행
        ryanArrows, // 라이언 점수표
        ryanScore + (10 - num), // 라이언이 득점!
        apeachScore, // 어피치 득점은 그대로
        leftArrow - ryanArrows[num] // 남은 화살은 사용한 화살 개수를 뺀다.
      )
      ryanArrows[num] = 0 // back : 원상복구
}

dfs(0, Array(11).fill(0), 0, 0, N)

 

 

② 라이언이 점수를 얻지 못하는 경우 (0발만 맞히는 경우)

라이언이 점수를 얻지 못하는 경우도 dfs 재귀호출을 진행해준다.

 

이 때 어피치도 화살을 맞히지 못한 경우일 때에는 둘 다 점수 획득이 없으며,

어피치가 화살을 맞힌 경우라면 어피치의 득점으로 처리한 후에 dfs 재귀 호출을 진행해주어야 한다.

// 2. dfs 함수 : num(과녁판 점수), ryanArrows(라이언 점수표), ryanscore(라이언 점수), apeachScore(어피치 점수), leftArrow(남은 화살)
function dfs(num, ryanArrows, ryanScore, apeachScore, leftArrow) {
    // 분기 3. 라이언이 점수를 얻지 못하는 경우 -> 어피치의 점수를 더해줌
    const apeachPoint = info[num] > 0 ? 10 - num : 0
    dfs(num + 1, ryanArrows, ryanScore, apeachScore + apeachPoint, leftArrow)
}

dfs(0, Array(11).fill(0), 0, 0, N)

 

 

2-2. 백트래킹 사용하기 (=> 유망성 확인 == dfs 탐색을 종료할 분기점 확인하기)

백트래킹을 사용하여 DFS 탐색의 종료 분기점을 잡아야 한다.

그렇지 않다면 call stack 무한 루프에 빠지게 된다..!

 

더 이상 dfs 탐색을 진행하지 않는 경우는 다음과 같다.

10점까지 모두 돌고 num이 11이 된 채로 dfs 호출이 진행되었다면, 남은 화살의 개수를 확인한다.

 

만약 남은 화살이 있는 경우라면 남은 화살이 0점을 맞추는 경우이기에 라이언의 점수표를 수정한다.

 

그리고 라이언과 어피치의 점수차이를 비교한다.

그리고 위에서 만들었던 헬퍼 함수 isBetterDiff를 사용하여 더 낮은 점수를 많이 맞힌 경우인지 확인한다.

현재 DFS 탐색을 진행하여 얻은 점수표 배열 ryanArrow이 더 좋은 배열(낮은 점수를 많이 맞힌 점수표)이거나

점수 차이가 더 크다면 결과값인 answer와 maxDiff를 수정한다.

 

남은 화살 개수를 0점에 넣었던 라이언의 점수표를 수정하고 return한다.

function dfs(num, ryanArrows, ryanScore, apeachScore, leftArrow) {
// 분기 1. 모든 점수를 다 돌았거나 화살을 다 쏜 경우
    if (num === 11) {
      // 2-1-1. 아직 남은 화살이 있는 경우(0점을 맞추는 경우) -> 남은 화살은 0점에 넣어줌
      if (leftArrow > 0) ryanArrows[10] += leftArrow

      // 2-1-2. 만약 점수 차이가 크다면, 결과값 수정하기 (점수차이, 라이언의 점수표)
      if (ryanScore > apeachScore) {
        const currentDiff = ryanScore - apeachScore
        if (
          currentDiff > maxDiff ||
          (currentDiff === maxDiff && isBetterDiff(ryanArrows, answer))
        ) {
          maxDiff = currentDiff // (결과값) 최대 점수 차이 수정
          answer = [...ryanArrows] // (결과값) 라이언의 점수표 수정
        }
      }

      if (leftArrow > 0) ryanArrows[10] -= leftArrow // 원상복구
      return
}

dfs(0, Array(11).fill(0), 0, 0, N)

 

 

 

3. 전체 코드

function solution(N, info) {
  // 0. 초기값 설정
  let answer = [-1] // 라이언의 점수표 배열 (전역변수)
  let maxDiff = 0 // 라이언과 어피치의 점수 차이 (전역변수)

  // 1. isBetterDiff 함수 : 둘 중 어떤 라이언의 점수표가 더 좋은 결과값인지 판단하는 함수
  //  ㄴ 낮은 과녁을 맞출수록 좋은 점수표
  function isBetterDiff(currentAnswer, maxAnswer) {
    for (let i = 10; i >= 0; i--) {
      if (currentAnswer[i] > maxAnswer[i]) return true
      if (currentAnswer[i] < maxAnswer[i]) return false
    }
    return false
  }

  // 2. dfs 함수 : num(과녁판 점수), ryanArrows(라이언 점수표), ryanscore(라이언 점수), apeachScore(어피치 점수), leftArrow(남은 화살)
  function dfs(num, ryanArrows, ryanScore, apeachScore, leftArrow) {
    // 분기 1. 모든 점수를 다 돌았거나 화살을 다 쏜 경우
    if (num === 11) {
      // 2-1-1. 아직 남은 화살이 있는 경우(0점을 맞추는 경우) -> 남은 화살은 0점에 넣어줌
      if (leftArrow > 0) ryanArrows[10] += leftArrow

      // 2-1-2. 만약 점수 차이가 크다면, 결과값 수정하기 (점수차이, 라이언의 점수표)
      if (ryanScore > apeachScore) {
        const currentDiff = ryanScore - apeachScore
        if (
          currentDiff > maxDiff ||
          (currentDiff === maxDiff && isBetterDiff(ryanArrows, answer))
        ) {
          maxDiff = currentDiff // (결과값) 최대 점수 차이 수정
          answer = [...ryanArrows] // (결과값) 라이언의 점수표 수정
        }
      }

      if (leftArrow > 0) ryanArrows[10] -= leftArrow // 원상복구
      return
    }

    // 분기 2. 라이언이 점수를 얻는 경우 -> 라이언의 점수를 더해줌
    if (leftArrow > info[num]) {
      ryanArrows[num] = info[num] + 1
      dfs(
        num + 1,
        ryanArrows,
        ryanScore + (10 - num),
        apeachScore,
        leftArrow - ryanArrows[num]
      )
      ryanArrows[num] = 0 // back : 원상복구
    }

    // 분기 3. 라이언이 점수를 얻지 못하는 경우 -> 어피치의 점수를 더해줌
    const apeachPoint = info[num] > 0 ? 10 - num : 0
    dfs(num + 1, ryanArrows, ryanScore, apeachScore + apeachPoint, leftArrow)
  }

  dfs(0, Array(11).fill(0), 0, 0, N)
  return answer
}

solution(5, [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0])
// [0,2,2,0,1,0,0,0,0,0,0]

// solution(1, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
// [-1]

// solution(9, [0, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1])
// [1,1,2,0,1,2,2,0,0,0,0]

// solution(10, [0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3])
// [1,1,1,1,1,1,1,1,0,0,2]

 

티스토리툴바