[프로그래머스] Java Lv2. 코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양궁대회

 

프로그래머스

문제설명

점수를 내는 방법은

• x점에 1번 사수가 y발을 맞혔을 경우 2번 사수는 y+1발 이상을 맞혀야 x점을 가져간다.
• x점을 y발을 맞혀도 x점만 가져간다.
• x점을 둘다 못맞히면 둘다 해당 점수를 자져가지 못한다.
• 최종 점수가 동점이면 1번 사수가 승리한다.

1번 사수가 활을 n발을 쏴서 1~10점까지의 점수에 각각 몇발을 맞혔는지가 주어진다.

이 때 2번사수가 가장 많은 점수차로 이기는 경우 각 점수에 몇발을 맞혔는지 배열로 반환하고 경우의 수가 없는 경우 -1을 반환하여야 한다.

같은 점수차가 여러 가지일 경우 가장 낮은 점수를 더 많이 맞힌 경우를 return한다.

제한사항

• 1 <= n <= 10
• info의 길이 = 11(0점 ~ 10점 11개)
• 0 <= info의 원소 <= n
• info의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살의 개수

접근방법

11개의 점수의 과녁에 최대 10개의 화살을 맞추는걸 전체탐색으로 고려해보면 중복조합으로 11H10의 경우의 수가 생기는데, 고정값이긴 하지만 경우의 수가 많아 다른 접근 방법이 필요해 보인다.

화살을 몇발을 맞히던 상관 없이 이 점수를 갖냐 못갖냐로 접근해본다. 이 때의 경우의 수는 2^11개이므로 전체탐색 할만한 개수다.

x점을 2번 사수가 갖기 위해선 1번 사수보다 1개만 더 맞히면 된다.

어떠한 점수를 획득하기로 결정된 경우의수에 필요한 화살의 개수를 구하고 이가 n개보다 크지 않다면 점수를 구한다.

이렇게 구한 점수의 최댓값을 구하면 된다.

점수차가 같은 케이스의 경우 최소점수를 더 많이 맞춘 경우를 반환해야 하니 남는 화살은 0점에 다 넣어준다.

핵심로직

• 각각의 점수를 획득 or 비획득 하는 경우를 판단해서 점수를 획득하기 위한 화살의 개수 배열을 반환
• 화살 개수 초과(다음 케이스로 continue) 및 미달시 0점에 화살 더해줌
• 사수 별 획득 점수 판단
• 2번 사수 승리 케이스일 경우 최대 점수차 여부 판단
• 최대 점수차가 기존과 같을 경우 낮은 점수를 더 많이 맞췄는지 판단
• 이기는 경우가 없을 경우 [-1] 반환

입출력 예

• n = 5
• info = [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
• result = [0, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0]

코드작성

class Solution {
    public int[] solution(int n, int[] info) {
        int[] bestAnswer = new int[11]; // 최종 답변 배열
        int maxScoreDifference = 0; // 최대 점수 차이

        // 1부터 2047(2^11 - 1)까지 점수 조합 탐색
        for (int combination = 1; combination < Math.pow(2, 11); combination++) {
            int[] currentAnswer = new int[11]; // 현재 점수 조합
            int arrowsUsed = 0; // 사용한 화살 개수

            // 점수 조합 선택 및 화살 개수 계산
            for (int i = 0; i < 10; i++) {
                if ((combination & (1 << i)) != 0) { // i번째 점수를 선택한 경우
                    currentAnswer[i] = info[i] + 1; // 최소 필요한 화살 개수
                    arrowsUsed += currentAnswer[i];
                }
            }

            // 화살 초과 시 제외
            if (arrowsUsed > n) continue;

            // 남은 화살은 0점에 배치
            currentAnswer[10] = n - arrowsUsed;

            // 점수 계산
            int lionScore = 0, apeachScore = 0;
            for (int i = 0; i < 11; i++) {
                if (currentAnswer[i] > info[i]) {
                    lionScore += 10 - i;
                } else if (info[i] > 0) {
                    apeachScore += 10 - i;
                }
            }

            // 점수 차이 비교 및 결과 갱신
            int scoreDifference = lionScore - apeachScore;
            if (scoreDifference > maxScoreDifference || (scoreDifference == maxScoreDifference && isBetterAnswer(currentAnswer, bestAnswer))) {
                maxScoreDifference = scoreDifference;
                bestAnswer = currentAnswer.clone();
            }
        }

        // 이길 수 없는 경우 -1 반환
        if (maxScoreDifference == 0) return new int[]{-1};

        return bestAnswer;
    }

    // 현재 답안이 더 나은지 비교하는 메서드 (더 낮은 점수를 우선으로)
    private boolean isBetterAnswer(int[] current, int[] best) {
        for (int i = 10; i >= 0; i--) {
            if (current[i] != best[i]) {
                return current[i] > best[i];
            }
        }
        return false;
    }
}