[백트레킹] 프로그래머스 양궁대회 자바 풀이

알아가야할 주요 내용

0. 본 문제는 완전탐색 문제로 백트레킹을 이용해야한다.
1. 문제의 조건 중 가장 큰 점수 차이가 여러개일 경우 가장 낮은 점수를 더 많이 맞힌 경우를 return 해야한다.
   ▶ 재귀함수로 라이언의 화살 배열을 채워갈때, 10번 index부터 시작하면 해당 조건을 고려하지 않고도 문제풀이가 가능하다.
2. 라이언 화살 배열의 값을 덮어 씌우기때문에 재귀함수 호출 전후로 라이언 화살 배열의 값을 원상복귀할 필요없다.
3. 재귀 호출을 위한 for 문안에서 라이언 화살 배열을 출력해 디버깅한다.

 

 

문제 풀이 코드

public class 양궁대회 {

    public static void main(String[] args) {
    	// 테스트 케이스
        Solution solution = new Solution();
        int[] info = new int[]{2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
        int n = 5;
        int[] solution1 = solution.solution(n, info);
        for (int i : solution1) {
            System.out.print(i + " ");
        }
        System.out.println();

        int[] info2 = new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int n2 = 1;
        int[] solution2 = solution.solution(n2, info2);
        for (int i : solution2) {
            System.out.print(i + " ");
        }
        System.out.println();

        int[] info3 = new int[]{0, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1};
        int n3 = 9;
        int[] solution3 = solution.solution(n3, info3);
        for (int i : solution3) {
            System.out.print(i + " ");
        }
    }

}

class Solution {
    static int[] lion = new int[11];
    static int[] peach = new int[11];
    static int maxValue = -1; // 라이언이 이길경우가 없을때 쓰기위한 변수
    static int[] answer = new int[11]; // 반환 배열

    public int[] solution(int n, int[] info) {
        peach = info.clone();
        comb(10, n); // 10번 인덱스(=depth)부터 채워나가기 위해 10 입력
        if(maxValue == -1)return new int[]{-1};
        return answer;
    }

    static void comb(int index, int leftArrowCount) { //바라보고있는 인덱스, 남은 화살 수
        if (index == -1) { // 모든 조합이 완성되었을떄
            int peachSum = 0; 
            int lionSum = 0;

            for (int i = 0; i < peach.length; i++) {
                if (lion[i] == 0 && peach[i] == 0) continue; // 서로 0일때는 계산X
                if (lion[i] > peach[i]) { // 라이언 점수 합계
                    lionSum += 10 - i;
                }
                if (lion[i] <= peach[i]) {
                    peachSum += 10 - i; // 피치 점수 합계
                }
            }
            if (lionSum > peachSum) { // 라이언 점수가 높을 경우에
            	// 기존의 점수차보다 현재 조합의 점수차가 높을 경우에
                if(Math.abs(lionSum - peachSum) > maxValue) { 
                    answer = lion.clone(); // 라이언 배열을 반환 배열로 복제
                    maxValue = lionSum - peachSum; // 점수차 변경
                }
            }
            return;

        } else {
            for (int i = leftArrowCount; i >= 0; i--) {
                lion[index] = i;	
                debug(lion);
                comb(index - 1, leftArrowCount - i);
            }

        }
    }
	
    // 디버깅 함수
    static void debug(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

 

프로그래머스 제출 코드

class Solution {
    static int[] lion = new int[11];
    static int[] peach = new int[11];
    static int maxValue = -1;
    static int[] answer = new int[11];

    public int[] solution(int n, int[] info) {
        peach = info.clone();
        comb(10, n);
        if(maxValue == -1)return new int[]{-1};
        return answer;
    }

    static void comb(int index, int leftArrowCount) {
        if (index == -1) {
            int peachSum = 0;
            int lionSum = 0;

            for (int i = 0; i < peach.length; i++) {
                if (lion[i] == 0 && peach[i] == 0) continue;
                if (lion[i] > peach[i]) {
                    lionSum += 10 - i;
                }
                if (lion[i] <= peach[i]) {
                    peachSum += 10 - i;
                }
            }

            if (lionSum > peachSum) {
                if(Math.abs(lionSum - peachSum) > maxValue) {
                    answer = lion.clone();
                    maxValue = lionSum - peachSum;
                }
            }
            return;

        } else {
            for (int i = leftArrowCount; i >= 0; i--) {
                lion[index] = i;
                //debug(lion);
                comb(index - 1, leftArrowCount - i);
            }

        }
    }

}