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

문제 설명

 

프로그래머스

 

접근 방법

우선 인자로 주어진 화살 n발에 대해서 백트래킹을 통해 라이언이 0점 ~ 10점에 대해 쏠 수 있는 모든 경우의 수를 탐색하도록 했습니다.

 

private void bow(int[] lionInfo, int index, int depth) {
        if (depth == n) {
            return;
        }

        for (int i = 0; i <= 10; i++) {
            if (index + i  < 11) {
                lionInfo[index + i]++;
                bow(lionInfo, index + i, depth + 1);
                lionInfo[index + i]--;
            }
        }
    }

 

즉, 라이언이 n발에 대해서 0점 과녁을 n발 맞춘 경우에서부터 10점 과녁을 n발 맞춘 경우까지 모든 경우의 수를 탐색하는 것입니다.

 

이후 다음 로직을 통해 위에서 구한 각각의 경우의 수에 대해 라이언과 어파치 간의 점수 차이를 구하도록 했습니다.

 

	private int getScoreGap(int[] apacheInfo, int[] lionInfo) {
        int apache = 0, lion = 0;

        for (int i = 0, score = 10; i < 11; i++, score--) {

            if (apacheInfo[i] == 0 && lionInfo[i] == 0) continue;

            if (apacheInfo[i] >= lionInfo[i]) {
                apache += score;
            } else {
                lion += score;
            }
        }

        return apache - lion;
    }

 

위에서 구한 점수 차이 결과상 라이언이 이겼을 경우(음수인 경우), 가장 높은 점수 차이로 이긴 경우의 수에 대해 결과값(라이언이 점수별 맞춘 개수)을 반복적으로 초기화해줍니다. 이때 만일 또 다른 경우의 수에서 이전과 동일한 점수 차이로 이긴 경우, 가장 낮은 점수를 맞힌 개수가 더 많은 경우의 수로 결과값을 초기화해줍니다.

 

    private void bow(int[] lionInfo, int index, int depth) {
        if (depth == n) {
            int temp = getScoreGap(info, lionInfo);

            if (temp < 0) {
                if (temp < scoreGap) {
                    scoreGap = temp;
                    result = lionInfo.clone();
                } else if (temp == scoreGap) {
                    if (validate(lionInfo)) {
                        result = lionInfo.clone();
                    }
                }
            }
            return;
        }
        
        // ...
    }

 

전체 소스 코드

class Solution {

    int scoreGap = 1, n;
    int[] info;
    int[] result;

    public int[] solution(int n, int[] info) {
        this.n = n;
        this.info = info;

        int[] lionInfo = new int[11];
        bow(lionInfo, 0, 0);

        if (scoreGap == 1) {
            return new int[]{-1};
        }

        return result;
    }

    private void bow(int[] lionInfo, int index, int depth) {
        if (depth == n) {
            int temp = getScoreGap(info, lionInfo);

            if (temp < 0) {
                if (temp < scoreGap) {
                    scoreGap = temp;
                    result = lionInfo.clone();
                } else if (temp == scoreGap) {
                    if (validate(lionInfo)) {
                        result = lionInfo.clone();
                    }
                }
            }
            return;
        }

        for (int i = 0; i <= 10; i++) {
            if (index + i  < 11) {
                lionInfo[index + i]++;
                bow(lionInfo, index + i, depth + 1);
                lionInfo[index + i]--;
            }
        }
    }

    private boolean validate(int[] lionInfo) {
        for (int i = 10; i > -1; i--) {

            if (result[i] == 0 && lionInfo[i] == 0) continue;

            if (lionInfo[i] > result[i]) {
                return true;
            } else if (lionInfo[i] < result[i]) {
                return false;
            }
        }

        return false;
    }

    private int getScoreGap(int[] apacheInfo, int[] lionInfo) {
        int apache = 0, lion = 0;

        for (int i = 0, score = 10; i < 11; i++, score--) {

            if (apacheInfo[i] == 0 && lionInfo[i] == 0) continue;

            if (apacheInfo[i] >= lionInfo[i]) {
                apache += score;
            } else {
                lion += score;
            }
        }

        return apache - lion;
    }
}

 

참고자료

• https://school.programmers.co.kr/learn/courses/30/lessons/92342