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

Link | 프로그래머스 92342번 문제 : 양궁대회

📌 About

점수의 개수의 11개이기 때문에 brute force으로 풀 수 있다.

백트래킹으로 10점부터 차례대로 탐색하면 된다.

📌 Solution

탐색을 할 때 이전 탐색 이후의 점수부터 탐색하면 된다.

만약 7번까지 탐색을 했다면 다음 탐색은 6번부터하면 된다.

만약 남은 화살이 peach가 맞춘 화살의 수보다 많으면 lion은 해당 점수에 한 개 더 명중한다.

백트래킹이기 때문에 재귀이후에는 다시 화살을 해당 점수에서 회수한다.

만약 화살의 개수가 0개라면 더 쏠 수 없기 때문에 최종 연산을 한다. (compare)

만약 화살이 남아있다면 다음 점수를 탐색한다.

for (int i = idx; i < peach.length; i++) {
    if (arrow > peach[i]) {
        lion[i] = peach[i] + 1;
        shoot(peach, lion, arrow - peach[i] - 1, i + 1);
        lion[i] = 0;
    } else if (arrow == 0) {
        compare(peach, lion, arrow);
        break;
    } else shoot(peach, lion, arrow, i + 1);
}

최종 연산은 다음과 같다.

private void compare(int[] peach, int[] lion, int arrow) {
    int diff = IntStream.rangeClosed(0, 10)
            .map(i -> lion[i] != 0 ? 10 - i : peach[i] != 0 ? i - 10 : 0).sum();
    if (maxDiff <= diff) {
        int[] lionRes = lion.clone();
        lionRes[10] += arrow;
        if (maxDiff == diff && result.length == 11) 
        	lionRes = compareResult(result, lionRes);
        maxDiff = diff;
        result = lionRes;
    }
}

지금까지 계산한 최대 점수 차이보다 현재 점수 차이가 작다면 넘어간다.

arrow를 다 쓰지 않고 최종 연산을 하는 경우도 있기 때문에 화살을 모두 쏜다.

만약 차이가 같다면 주어진 제한사항에 맞게 적은 점수에 더 많이 맞춘 것을 선택한다.

private int[] compareResult(int[] lionA, int[] lionB) {
    for (int i = 10; i >= 0; i--)
        if (lionA[i] != lionB[i])
            return lionA[i] > lionB[i] ? lionA : lionB;
    return result;
}

📌 Code

GitHub Repository

import java.util.stream.IntStream;

class Solution {

    int maxDiff = 1;
    int[] result = {-1};

    public int[] solution(int n, int[] info) {
        shoot(info, IntStream.generate(() -> 0).limit(11).toArray(), n, 0);
        return result;
    }

    private void shoot(int[] peach, int[] lion, int arrow, int idx) {
        if (idx == 11) compare(peach, lion, arrow);
        else for (int i = idx; i < peach.length; i++) {
            if (arrow > peach[i]) {
                lion[i] = peach[i] + 1;
                shoot(peach, lion, arrow - peach[i] - 1, i + 1);
                lion[i] = 0;
            } else if (arrow == 0) {
                compare(peach, lion, arrow);
                break;
            } else shoot(peach, lion, arrow, i + 1);
        }
    }

    private void compare(int[] peach, int[] lion, int arrow) {
        int diff = IntStream.rangeClosed(0, 10)
                .map(i -> lion[i] != 0 ? 10 - i : peach[i] != 0 ? i - 10 : 0).sum();
        if (maxDiff <= diff) {
            int[] lionRes = lion.clone();
            lionRes[10] += arrow;
            if (maxDiff == diff && result.length == 11) 
                lionRes = compareResult(result, lionRes);
            maxDiff = diff;
            result = lionRes;
        }
    }

    private int[] compareResult(int[] lionA, int[] lionB) {
        for (int i = 10; i >= 0; i--)
            if (lionA[i] != lionB[i])
                return lionA[i] > lionB[i] ? lionA : lionB;
        return result;
    }
}