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

프로그래머스 양궁대회 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92342

라이언이 k점(1≤k≤10)을 득점하기 위해서는, 어피치보다 k점에 더 많은 화살을 쏴야 한다.
그리고 문제 중 이런 조건이 있다.

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우,
가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

어피치보다 k점에 한 발을 더 쏘든 두 발을 더 쏘든 얻어가는 점수는 같다.
어피치와 같은 개수를 쏘거나 0개를 쏘거나 득점하지 못하는 건 마찬가지이다.

따라서, 어피치보다 딱 한 발을 더 쏴서 득점하거나, 0발을 쏴서 득점하지 않는 케이스만 고려한다.
1점부터 10점까지 2^10 = 1024개의 경우의 수를 고려하는 방식으로 구현했다.
(1점부터 10점까지 쏘고 남은 화살은 0점에 몰아준다.)

class Solution {
    public int[] solution(int n, int[] apeach) {
        
        final int len = 11;
        
        int[] answer = {-1};
        int[] ryan = new int[len];
        for(int i = 0 ; i < len ; i++)
            ryan[i] = apeach[i] + 1;
        
        int maxDiff = 0;
        int solutionIndex = -1;
        
        int numOfCases = 2<<len-1;
        
        for(int i = 0 ; i < numOfCases ; i++){
            int apeachCount = 0;
            int ryanCount = 0;
            int apeachScore = 0;
            int ryanScore = 0;
            
            for(int j = 0 ; j < len-1 ; j++){
                if((i&1<<len-2-j) == 0 && apeach[j] > 0){
                    apeachScore += 10-j;
                } else if((i&1<<len-2-j) > 0){
                    ryanScore += 10-j;
                    ryanCount += ryan[j];
                }
            }
            if(ryanCount <= n){
                int thisDiff = ryanScore - apeachScore;
                if(thisDiff > maxDiff){
                    maxDiff = thisDiff;
                    solutionIndex = i;
                } else if(maxDiff > 0 && thisDiff == maxDiff){
                    int lastRyanZeroCount = solutionIndex&1;
                    int thisRyanZeroCount = n - ryanCount;
                    if(thisRyanZeroCount > lastRyanZeroCount){
                        solutionIndex = i;
                    } else if(thisRyanZeroCount == lastRyanZeroCount){
                        for(int j = 0 ; j < len-1 ; j++){
                            if ((i&1<<j) > (solutionIndex&1<<j)){
                                solutionIndex = i;
                                break;
                            } else if((i&1<<j) < (solutionIndex&1<<j))
                                break;
                        }
                    }
                }
            } 
        }
        
        if(maxDiff > 0){
            answer = new int[len];
            int remainder = n;
            for(int i = 0 ; i < len-1 ; i++){
                if((solutionIndex&1<<len-2-i) > 0){
                    answer[i] = ryan[i];
                    remainder -= ryan[i];
                } else answer[i] = 0;
            }
            answer[len-1] = remainder;
        }
        
        return answer;
    }
}

1024가지로 케이스가 많지 않다보니, 모든 케이스에 대해 연산해도 수행속도에 따른 문제는 없었다.
다만 중복 연산이 여러 차례 수행된다는 점, 불필요한 연산까지 수행하게 된다는 점이 아쉽다.

이를 보완하기 위해 백트래킹 기법을 사용할 수 있고, 실제로 많은 분들이 백트래킹으로 문제를 푸셨다.
기회가 된다면 이 점을 보완해 다시 구현해보고싶다.