[프로그래머스] 양궁대회 (Java)

프로그래머스 : 양궁대회 (Java)

문제

문제 확인하기

풀이

과녁은 0 ~ 10점까지 총 11가지의 점수가 있다.
이 11가지의 점수 중 획득할 수 있는 점수들의 조합은 2^11(2048)이므로, 우리는 완전 탐색을 통해 문제를 해결할 수 있다.

여기서 점수를 획득할지 안할지 기록하기 위해 비트마스킹 기법을 활용하였다.

획득 가능한 점수들의 조합을 반복문으로 돌면서 해당 점수를 얻을 때 사용한 화살 개수가 문제에서 주어진 화살 개수 n보다 작거나 같을 때에만 라이언이 획득한 점수와 어피치가 획득한 점수를 계산하도록 하였다.
현재 확인하고있는 점수들의 조합을 얻기 위해 n발의 화살보다 크다면 불가능한 경우의 수이기 때문이다.

현재 확인하고 있는 점수들의 조합이 라이언이 쏠 수 있는 경우의 수라면, 어피치와 라이언이 얻는 점수를 계산하여 이 점수들의 차를 계산한다.
둘의 점수 차는 더 큰 쪽을 따로 기록해두도록 하였다.
문제에서 주어진 조건 중 하나가 가장 큰 점수차로 라이언이 이기는 경우를 원하였기 때문이다.

점수 차가 같은 경우에는, 문제에서 주어진 조건에 따라서, 이전에 확인한 점수들의 조합(a라고 하겠다)과 현재 확인하고 있는 점수들의 조합(b라고 하겠다) 중 더 작은 점수를 많이 맞힌 경우를 정답으로 해야한다.
먼저 a와 b의 경우 각각 쏜 화살의 갯수를 카운팅하고, 더 적게 쏜 경우를 기록하도록 하였다.
얻을 수 있는 점수는 0 ~ 10점까지이고, 문제에서 가장 낮은 점수를 더 많이 맞힌 경우를 정답으로 하라고 하였다.
0 ~ 10점 중 가장 낮은 점수는 0점이다.
더 적게 쏜 경우가 더 많은 화살이 남았다는 뜻이고, 남는 화살은 0점에 쏜다고 가정하면, 해당 경우가 가장 낮은 점수를 더 많이 맞힌 경우가 된다.

남은 화살 수가 같다면, 0점부터 10점까지 차례로 확인하면서 낮은 점수를 더 많이 맞힌 경우, 해당 경우를 기록해두고 두 경우의 비교를 종료한다.
0 -> 1 -> 2 -> ... 순으로 비교를 할 때 0점의 경우는 동일하고, 1점에서 a가 더 많이 맞혔다면 가장 낮은 점수를 더 많이 맞힌 경우는 a가 되기 때문이다.

위 과정을 통해 모든 가능한 조합을 탐색하면 기록해둔 수를 배열로 변환하여 정답으로 반환하면 된다.
만약 기록해둔 수가 변경이 안되었다면, 어떤 경우에도 라이언이 이길 수 없다는 뜻이기 때문에 [-1]을 정답으로 반환한다.

자바로 작성한 풀이 코드는 다음과 같다.

class Solution {
    public int[] solution(int n, int[] info) {
        int[] answer;
        // 최대 차이 기록
        int maxSub = 0;
        // 최대 차이일 때 라이언이 점수를 얻을 배열 bitmask
        int resultNum = 0;
        // 라이언이 쏜 화살 개수 카운팅
        int count;
        for (int i = (1 << info.length) - 1; i >= 0; i--) {
            count = 0;
            // j = 10 부터 시작
            for (int j = info.length - 1; j >= 0; j--) {
                // j 번째를 쏜다고 결정 되었다면 화살 수 카운팅
                if ((i & (1 << j)) > 0) {
                    count += (info[info.length - 1 - j] + 1);
                }
            }
            // 주어진 화살 수 보다 같거나 작아야 가능
            if (count <= n) {
                // 어피치 점수 계산을 위해 이진수 변환
                int ryanNum = i;
                int apeachNum = calApeachNum(ryanNum, info);

                // 라이언 어피치 점수 계산 : 비트수 -> 점수로 변환
                int ryanScore = calScore(ryanNum);
                int apeachScore = calScore(apeachNum);
                // 둘의 점수차
                int currentSub = ryanScore - apeachScore;
                // 라이언이 더 커야 이김
                if (currentSub > 0) {
                    // 현재 점수 차가 이전에 기록된 값보다 크면 교체
                    if (currentSub > maxSub) {
                        maxSub = currentSub;
                        resultNum = ryanNum;
                    }
                    // 점수 차가 같으면
                    if (currentSub == maxSub) {
                        // 비교해서 적은 점수를 더 많이 맞힌 수로 기록
                        resultNum = compare(ryanNum, resultNum, info);
                    }
                }
            }
        }

        // 결과 숫자가 0 이면 이길 수 없다는 뜻.
        if (resultNum == 0) {
            return new int[]{-1};
        }

        count = n;
        answer = new int[info.length];
        for (int i = 0; i < answer.length - 1; i++) {
            // i 번째 점수(i=0 -> 점수=10, i=10 -> 점수=0)를 얻는다면,
            // 어피치가 해당 점수에 맞힌 화살 + 1 만큼 라이언의 화살 갯수 차감
            if ((resultNum & (1 << (answer.length - 1 - i))) > 0) {
                // 어피치가 해당 점수에 맞힌 화살 + 1
                int now = info[i] + 1;
                answer[i] = now;
                count -= now;
            }
        }
        // 라이언이 쏠 수 있는 화살이 남았다면
        if (count > 0) {
            // 0점에 모두 쏜다.
            answer[answer.length - 1] = count;
        }

        return answer;
    }

    // 획득할 점수를 기록한 비트 넘버를 통해 총점 계산
    private int calScore(int num) {
        int score = 0;
        for (int i = 10; i >= 0; i--) {
            if ((num & (1 << i)) > 0) {
                score += i;
            }
        }
        return score;
    }

    // 라이언이 ryanNum 비트의 점수를 얻을 때, 어피치가 얻는 점수의 비트 넘버
    private int calApeachNum(int ryanScore, int[] info) {
        int apeachNum = 0;
        for (int i = info.length - 1; i >= 0; i--) {
            if (info[info.length - 1 - i] > 0) {
                apeachNum += (1 << (i));
            }
        }
        return apeachNum & (apeachNum ^ ryanNum);
    }

    // a, b 비트 중 어떤 수가 더 적은 점수를 많이 맞혔는지 비교
    private int compare(int n, int a, int b, int[] info) {
        // a가 쏜 화살 카운팅
        int aArrow = 0;
        // b가 쏜 화살 카운팅
        int bArrow = 0;
        for (int i = 0; i < 11; i++) {
            if ((a & (1 << 10 - i)) > 0) {
                aArrow += (info[i] + 1);
            }
            if ((b & (1 << 10 - i)) > 0) {
                bArrow += (info[i] + 1);
            }
        }

        // a에 쏜 화살이 더 많다면 b가 0점이 더 많음. b 반환
        if (aArrow > bArrow) {
            return b;
        }
        // b에 쏜 화살이 더 많다면 a가 0점이 더 많음. a 반환
        else if (aArrow < bArrow) {
            return a;
        }
        // a,b 쏜 화살이 같다면
        else {
            // 0점부터 맞힌 수 카운팅
            for (int i = info.length - 1; i >= 0; i--) {
                // a일 때 (10-i)점을 맞힌 화살 수
                int ai = (a & (1 << 10 - i)) > 0 ? info[i] + 1 : 0;
                // b일 때 (10-i)점을 맞힌 화살 수
                int bi = (b & (1 << 10 - i)) > 0 ? info[i] + 1 : 0;
                // i점을 a가 더 많이 맞혔다면 a 반환
                if (ai > bi) {
                    return a;
                }
                // i점을 b가 더 많이 맞혔다면 b 반환
                if (bi > ai) {
                    return b;
                }
            }
        }

        // a, b가 같은 수 일때 -> 같은 수가 될 수 없음. 컴파일 오류 해결을 위함
        return 0;
    }
}