[알고리즘 TIL] 양궁 대회

문제

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

프로그래머스 LV2. 시뮬레이션

설명

이 문제의 핵심은, 중복 조합의 경우의 수를 탐색하는 코드를 구현하는 것이다.

중복 조합의 경우의 수를 탐색하는 코드는 다음과 같다.

while (true) {
                //수행할 로직
                ...
                //다음 조합 생성
                //마지막 요소부터 확인
                int index = n - 1;
                while (index >= 0 && combinations[index] == 10) {
                    //10이면 왼쪽 요소로 이동
                    index--;
                }
                //모든 조합을 탐색했으면 종료
                if (index < 0) break;
                //증가 가능한 위치에서 값 증가
                combinations[index]++;
                //증가한 값으로 나머지 채우기
                for (int i = index + 1; i < n; i++) {
                    combinations[i] = combinations[index];
                }
            }

combinations 배열에는 내가 선택한 숫자를 저장한다. 만약, 10점, 9점 두 번, 8점 2번이라면, [8,8,9,9,10]이 저장된다.

combinations 배열은 맨 처음에 모두 0점을 맞추는 것으로 초기화한다. 그 후 맨 마지막 요소부터 숫자를 증가시킨다. 

중복 조합, 즉 순서가 상관 없기 때문에, 앞 요소로 이동 후 숫자를 증가시킨 경우에는 지금까지 지나온 인덱스의 숫자는 증가된 숫자로 모두 초기화한 후, 다시 반복한다.

구현

import java.util.*;

public class Q_양궁대회 {

    static int maxDifference = -100;
    static int[] lionInfo;

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] info = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3};
        int n = 10;
        int[] answer = solution.solution(n, info);
        System.out.println(Arrays.toString(answer));
    }

    static class Solution {
        public int[] solution(int n, int[] info) {
            int[] answer = new int[]{-1};
            int[] combinations = new int[n]; //뽑을 점수 저장 배열
            //처음 시작은 0점만 맞춘 경우 [0,0,0,0,0]
            Arrays.fill(combinations, 0);

            while (true) {
                //수행할 로직
                int scoreDifference = calculateScore(info, combinations);
                if (scoreDifference >0 && scoreDifference > maxDifference) {
                    maxDifference = scoreDifference;
                    answer = lionInfo.clone();
                } else if (scoreDifference == maxDifference) {
                    if (isContainWithLowerScores(answer))
                        answer = lionInfo.clone();
                }
                //다음 조합 생성
                //마지막 요소부터 확인
                int index = n - 1;
                while (index >= 0 && combinations[index] == 10) {
                    //10이면 왼쪽 요소로 이동
                    index--;
                }
                //모든 조합을 탐색했으면 종료
                if (index < 0) break;
                //증가 가능한 위치에서 값 증가
                combinations[index]++;
                //증가한 값으로 나머지 채우기
                for (int i = index + 1; i < n; i++) {
                    combinations[i] = combinations[index];
                }
            }

            return answer;
        }

        private boolean isContainWithLowerScores(int[] answer) {
            for (int i = 10; i >=0; i--) {
                if (lionInfo[i] < answer[i]) {
                    return false; // 하나라도 answer[i]보다 작은 값이 있다면 false
                }
            }
            return true;
        }

        private int calculateScore(int[] apeachInfo, int[] combinations) {
            int apeachScore = 0;
            int lionScore = 0;
            lionInfo = new int[11];

            for (int i = 0; i < combinations.length; i++) {
                int score = combinations[i];
                int index = 10 - score;
                lionInfo[index]++;
            }

            for (int i = 0; i < 11; i++) {
                if (apeachInfo[i] ==0 && lionInfo[i] == 0) continue;
                if (apeachInfo[i] >= lionInfo[i]) apeachScore += 10-i;
                else lionScore += 10-i;
            }
            
            return lionScore - apeachScore;
        }
    }
}