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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

라이언이 가장 큰 점수차로 우승하는 경우의 점수 리스트를 찾는 문제이다.

 

큰 점수차를 내기 위해선 최대한 화살을 효율적으로 써야 한다. 즉, 다음의 원칙을 지키며 화살을 쏴야 한다.

• 얻을 점수라면 어피치보다 딱 한발 더 쏜다.
• 버릴 점수라면 한발도 쏘지 않는다.

점수는 10~0, 총 11가지이며 각 점수를 얻을 수도 있고 버릴 수도 있다.

즉, 각 점수에 대한 선택지는 2가지인 셈이다.

이렇게 라이언이 각 점수를 얻거나 버리거나 해서 발생하는 모든 경우의 수를 따져야 한다.

모든 경우의 수를 따진다는 점에서 깊이 우선 탐색(DFS)을 떠올릴 수 있다.

 

단, 한 가지 경우에서는 백트래킹해야 한다.

그 경우는 바로 화살을 다 쏜 경우이다.

탐색을 하다가 화살의 갯수가 0이 되면 나머지 탐색을 할 필요가 없이 종료한다.

이렇게 탐색의 효율을 늘릴 수 있다.

 

주의해야할 점

이렇게 기본적인 문제의 흐름 파악은 끝났다. 바로 구현하면 될 것 같지만 이 문제에는 함정이 있다.

크게 두 가지가 있는데

 

첫 번째는 점수의 차이가 같은 경우이다.

만약 점수차이가 같다면 가장 작은 점수를 더 많이 쏜 케이스가 답이 된다. 

예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return해야 한다.

이 부분은 문제에도 나와있는 사항이라 실수하는 사람이 적을 것이다.

 

두 번째는 최종 점수가 같은 케이스이다.

언뜻 보면 특정 점수에 대해 쏜 화살의 갯수가 같아도 어피치가 이기기 때문에 최종점수가 같은 케이스가 없다고 생각할 수 있는데

N: 3, info: [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]인 경우에 라이언이 10점, 7점을 얻고 어피치가 9점 8점을 얻으면 점수가 17점으로 같게 된다.

이 부분은 코딩할 때 주의해야할 부분이라고 할 수 있는데 어떻게 코딩하느냐에 따라 전혀 문제가 될 수도 없는 부분이다.

이 부분이 왜 문제가 될 수가 있는지는 아래 코드를 설명하면서 다시 이야기 하도록 하겠다.

3. 내 코드

---

import java.util.*;

class Solution {

    private int max_diff;
    private int[] max_list;
    private int[] apeach;

    public int[] solution(int n, int[] info) {
        max_diff = 0;
        max_list = new int[11];
        apeach = info;
        calScore(new int[11], n, 10);

        return max_diff == 0 ? new int[]{-1} : max_list;
    }

    private void calScore(int[] lion, int n, int score) {

        // 남은 화살이 0발일때 점수 산정
        if (n == 0) {
            checkWinner(lion);
            return;
        }

        // 현재 점수가 -1일때 점수 산정
        if (score < 0) {
            // 남아 있는 화살 0점에 분배
            lion[10] = n;
            checkWinner(lion);
            return;
        }

        // 라이언이 해당 점수를 얻는 경우 어피치보다 해당 점수를 한발 더 쏴야 함

        if (apeach[10 - score] < n) { // 화살이 남아있다면
            int[] newList = lion.clone();
            newList[10 - score] = apeach[10 - score] + 1;
            calScore(newList, n - newList[10 - score], score - 1);
            newList[10 - score] = 0; // 다시 화살 안쏨 처리
        }

        // 라이언이 해당 점수를 얻지 않는 경우 해당 점수는 0발 쏨
        calScore(lion, n, score - 1);


    }

    private void checkWinner(int[] lion) {
        int lion_score = 0;
        int apeach_score = 0;
        for (int i = 0; i < lion.length; i++) {
            if (apeach[i] > lion[i])
                apeach_score += 10 - i;
            else if (lion[i] > apeach[i])
                lion_score += 10 - i;
        }
        if (lion_score - apeach_score > max_diff) {
            max_list = lion.clone();
            max_diff = lion_score - apeach_score;
        } else if (lion_score - apeach_score == max_diff) {
            for (int i = 10; i >= 0; i--) {
                if (max_list[i] < lion[i]) {
                    max_list = lion.clone();
                    break;
                } else if (max_list[i] > lion[i]) {
                    break;
                }
            }
        }
    }
}

시간 복잡도

• O(2^11)

0부터 10까지 각 점수를 얻거나 얻지 않는 두 가지 케이스가 있으므로 O(2^11)이다. 

단, 화살을 다 쏜 경우 백트래킹하기 때문에 실제 효율은 이보다 좋다.

 

최종 점수가 같은 케이스

위에서 최종 점수가 같으면 문제가 될 수도 있다고 했는데 그 이유를 이야기하도록 하겠다.

문제가 발생할 수 있는 부분은 checkWinner()의 다음 부분이다.

if (lion_score - apeach_score > max_diff) {
    max_list = lion.clone();
    max_diff = lion_score - apeach_score;
} else if (lion_score - apeach_score == max_diff) {
    for (int i = 10; i >= 0; i--) {
        if (max_list[i] < lion[i]) {
            max_list = lion.clone();
            break;
        } else if (max_list[i] > lion[i]) {
            break;
        }
    }
}

이중에서도 if(max_list[i] < lion)에서 문제가 발생할 수 있는데

바로 max_list를 초기화하지 않는 경우 문제가 발생한다.

// max_list = new int[11];

사실 대부분의 케이스에선 max_list를 초기화하지 않아도 된다

왜냐하면 처음부터 라이언과 어피치의 점수가 같은 경우는 거의 나오지 않기 때문이다.

그렇기에 해당 부분에 의해 max_list가 자동으로 생성된다.

if (lion_score - apeach_score > max_diff) {
    max_list = lion.clone();
    max_diff = lion_score - apeach_score;
}

 

하지만 처음부터 라이언과 어피치의 점수가 같게 되면 다음 부분부터 호출되기 때문에 NullPointerException이 발생하게 된다.

else if (lion_score - apeach_score == max_diff) {
for (int i = 10; i >= 0; i--) {
    if (max_list[i] < lion[i]) {
        max_list = lion.clone();
        break;
    } else if (max_list[i] > lion[i]) {
        break;
    }
}

 

 

이래서 교수님이 변수는 반드시 초기화하라고 하셨나보다...

4. 피드백

---

• 모든 경우의 수를 파악할땐 깊이 우선 탐색
• 특정 조건을 통해 백트래킹을 해서 탐색의 효율을 늘리자
• 모든 변수는 초기화부터하고 사용하자
• 재귀에서 인자로 배열을 다룰 때 새로운 배열을 하나 생성해 복사한후 넘겨줘야 한다.
  그래야 원래 배열의 값을 해치지 않는다.