프로그래머스 2023 KAKAO BLIND RECRUITMENT 양궁대회 [JAVA] - 23년 8월 26일

복습 문제인데 전에 풀었을때보다 시간이 더 걸렸다. ㅜㅜ
3시간 동안 문제를 잡고 있었는데 2시간을 디버깅으로 시간을 썼다. (sout만 찍어서 디버깅 하려니까 정말 어렵다)

괜히 전에 풀어봤다고 문제 이해를 제대로 안 하고 풀다가 이상하게 풀이를 진행했고, 그러다보니 디버깅 하는게 시간이 엄청 오래 걸렸다. (역시 대부분의 문제는 내가 맞다고 생각한 부분이 문제가 된다.)

그래도 테스트 시간을 비교해보니 전에보다 시간이 많이 줄어들었다 ! => 코드는 그나마 조금 더 효율적으로 짯다🤣

import java.util.Arrays;

/*
아이디어
- 보통 1~10 사이의 값 -> 백트래킹을 많이 쓴다. (재귀함수)
- 내가 최대한의 점수 차로 이길 수 있는 모든 경우의 수를 구한다.
- 여러 값이 있으면 가장 낮은 점수로 이긴 경우를 고르고 반환.

- 라이언은 이기기 위해서 무조건 1발을 더 써야한다.
- 이기지 못 할 꺼면 한발이라도 안쓰는게 낫다.
- 나올 수 있는 경우의 수가 엄청 많을 것 같다 => 백트래킹을 써서 완전탐색 (모든 경우의 수를 확인) -> 라이언이 이기거나, 지거나 이렇게 범위 나눠서 진행하자.

시간복잡도
- 완전 탐색 (백트래킹) -> O(n ^ n)

자료구조
- 사용하는 값들이 모두 작으니 int를 쓰자.
 */


class Solution {
    private int[] answer;
    private int[] apeachScores;
    private int curMaxDiff;
    private int LAST_INDEX = 10;

    public int[] solution(int maxArrowCnt, int[] info) {
        //재귀를 돌면서 모든 경우의 수를 구한다.
        answer = new int[]{-1};

        apeachScores = info;
        curMaxDiff = 0;

        int curIndex = 0;
        int[] rionInfo = new int[info.length];
        backTracking(curIndex, rionInfo, maxArrowCnt);

        return curMaxDiff == 0 ? new int[]{-1} : answer;
    }

    private void backTracking(final int curIndex, final int[] rionInfo, final int curArrowCnt) {
        if (curIndex == LAST_INDEX) { //화살이 남았는데 마지막 Index에 도달한 경우
            if (curArrowCnt > 0) {
                rionInfo[curIndex] = curArrowCnt;
            }

            //점수 계산을 해서 curMaxScore 크면 answers에 저장.
            final int curDiff = calculateScoreDiff(rionInfo);

            if (curDiff == 0) {
                rionInfo[curIndex] = 0;
                return;
            }

            if (curDiff > curMaxDiff) {
                curMaxDiff = curDiff;
                answer = Arrays.copyOf(rionInfo, rionInfo.length);
            } else if (curDiff == curMaxDiff) {
                //answer가 업데이트 됐으면 우선순위 비교
                answer = calculatePriority(answer, rionInfo);
            }

            rionInfo[curIndex] = 0;
            return;
        }

        //이기고, 지고의 모든 경우의 수를 구하자.
        for (int idx = 0; idx < 2; idx++) {
            if (idx == 0) { // 이기는 경우
                final int apeachShootArrowCnt = apeachScores[curIndex];

                //이기려면 어피치보다 1개 더 쏴야함
                //화살 수가 적으면 못 쏨
                final int rionShootArrowCnt = apeachShootArrowCnt + 1;
                if (curArrowCnt >= rionShootArrowCnt) {
                    rionInfo[curIndex] = rionShootArrowCnt;

                    //다음 라운드 진행
                    backTracking(curIndex + 1, rionInfo, curArrowCnt - rionShootArrowCnt);

                    //백트래킹은 경우 확인했으면 원래대로 돌려놔야함
                    rionInfo[curIndex] = 0;

                    continue;
                }
            }

            //지는 경우 (화살이 부족한 경우에도 지는 걸로 친다.)
            backTracking(curIndex + 1, rionInfo, curArrowCnt);
        }
    }

    private int[] calculatePriority(final int[] oldArr, final int[] newArr) {
        for (int i = oldArr.length - 1; i >= 0; i--) {
            if (newArr[i] > oldArr[i]) {
                return Arrays.copyOf(newArr, newArr.length);
            } else if (newArr[i] < oldArr[i]) {
                return oldArr;
            }
        }

        return oldArr;
    }

    private int calculateScoreDiff(final int[] rionScores) {
        int apeachTotalScore = 0;
        int rionTotalScore = 0;

        //10점에서부터 비교하면서 크면 점수 추가
        for (int scoreIdx = 0; scoreIdx < rionScores.length; scoreIdx++) {
            final int apeachCurrentIndexArrowCount = apeachScores[scoreIdx];
            final int rionCurrentIndexArrowCount = rionScores[scoreIdx];

            if (apeachCurrentIndexArrowCount == 0 && rionCurrentIndexArrowCount == 0) {
                continue;
            }

            final int curScore = 10 - scoreIdx;

            if (rionCurrentIndexArrowCount > apeachCurrentIndexArrowCount) {
                rionTotalScore += curScore;
                continue;
            }

            apeachTotalScore += curScore;
        }

        return Math.max(rionTotalScore - apeachTotalScore, 0);
    }
}