양궁대회(2022 KAKAO BLIND RECRUITMENT)

문제

코드

class Solution {
    static int difference=0;
    static int[] answer=new int[11];
    static int[] apeachResult;
    
    public int[] solution(int n, int[] info) {
        apeachResult=info;
        int[] target=new int[11];
        dfs(target,n,0);
            
        if(difference==0){
            int arr[]={-1};
            return arr;
        }
        return answer;
    }
    public static void dfs(int[] target,int leftArrow,int index){
        if(leftArrow==0){
            int lion=0;
            int apeach=0;
            for(int i=0;i<11;i++){
                if(target[i]==0&&apeachResult[i]==0) continue;
                if(target[i]>apeachResult[i]) lion+=10-i;
                else apeach+=10-i;
            }
            if(difference<lion-apeach){
                difference=lion-apeach;
                answer=target;
                return;
            }
            else if(difference==lion-apeach){
                for(int i=10;i>=0;i--){
                    if(target[i]>answer[i]){
                        answer=target;
                        return;
                    }
                    else if(target[i]<answer[i]) return;
                    else continue;
                }
            }
            else return;
        }
        if(index==10){
            target[10]+=leftArrow;
            dfs(target,0,index);
        }
        else{
            int[] winTarget=target.clone();
            int[] loseTarget=target.clone();
            winTarget[index]=apeachResult[index]+1;
            if(leftArrow-winTarget[index]>=0)
                dfs(winTarget,leftArrow-winTarget[index],index+1);
            dfs(loseTarget,leftArrow,index+1);
        }
    }
}

풀이

(1) 전체적인 흐름은 dfs를 통해 라이언이 얻을 수 있는 모든 점수를 탐색한 후 한번 탐색이 끝날때마다 어피치와 라이언 의 결과를 채점 후, 점수차를 구해 결과를 새로 갱신한다.
(2) 점수차이가 기존에 갱신되어있던 점수차이보다 크면 새로 갱신하고, 같으면 문제에서 나왔듯이 낮은 점수가 더 많은 결과 배열을 갱신한다.
(3) 완전탐색을 하는 과정은 다음과 같다.

• index변수 ex)index=0 이면 10점 과녁에 대해 라이언이 점수를 얻을 것인지 줄 것인지를 결정한다.
• index당 경우의 수는 2개이다. 점수를 얻거나, 받거나.
• 점수를 얻는 경우에는 어피치보다 한번 더 맞추는 것이 가장 효율적이다.
• 점수를 줄 때에는 아예 맞추지 않는 것이 가장 효율적이다.
• 위의 두가지 경우에 대해 index를 늘려가며 재귀호출을 해준다.
• 인덱스가 10이 되었는데도 남은 화살이 남아있는 경우에는 가장 낮은점수(0점)에 나머지를 활을 모두 쏘도록 한다.

결과

이 문제에 시간을 정말 많이 소요했다. 처음에는 위와 같은 풀이가 아니었다. 정말 라이언이 쏠수있는 화살의 모든 경우의수를 하나하나 다 검사하려 했다. 그래서 처음에는 StackOverFlow가 발생했다.
그래서 재귀호출 수를 줄이는 방법을 생각해야 했다. 모든 경우의 수를 생각하되, 몇가지 제한 조건(예를 들어, 라이온이 10점에 대해 쏜 화살의 개수가 어피치가 많은 경우, 10점은 더이상 쏘지 않는다)을 작성해 주었다. 하지만 정확성이 70정도가 나와 정답을 맞추지 못했다.
그래서 라이언이 쏠 수 있는 경우의 수를 좀 더 효율적으로 탐색하는 경우를 다시 생각해야 했다.
생각해 보면 점수별로 라이언이 쏴야하는 화살의 수는 이미 정해져 있었다. 점수는 얻는 경우에는 어피치보다 1개 더 많이 쏘면 되고, 점수를 얻지 못하는 경우에는 아예 안쏘면 된다.
이렇게 해야 가장 효율적으로 경우의 수를 계산할 수 있었다.
각각 점수 별로 이 점수에 대해 라이언이 얻을건지 어피치가 얻을건지에 대해서만 재귀호출 해주면 된다.

지금부터는 공부를 하면서 chatGPT를 좀 활용해보려고 한다. 문제를 다 풀고 chatGPT에게 코드 리뷰를 맡기면 다음과 같이 문제점을 분석해준다. 완벽하게 분석해주진 않지만 나름대로 많은 도움이 될 것 같다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges