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

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

코딩테스트 연습 - 양궁대회

class Solution {
    static int[] win=new int[11];
    static boolean[] check=new boolean[11];
    static int max=0;
    static int[] answer=new int[11];
    static int N;
    static int nums;
    static int[] sinfo;
    public int[] solution(int n, int[] info) {
        N=n;
        sinfo=info;
        for (int i=0; i<info.length; i++){
            win[i]=info[i]+1;
        }
        for (int i=1; i<=info.length-1; i++){
            comb(0,0,i);
        }
        if (max==0){
            int[] temp=new int[1];
            temp[0]=-1;
            return temp;
        }
        else{
            return answer;
        }
    }
    
    public void comb(int idx, int cnt, int pick){
        if (cnt==pick){
            if (isPossible()){
                calc();
            }
            return;
        }
        for (int i=idx; i<check.length-1; i++){
            if (check[i]){
                continue;
            }
            check[i]=true;
            comb(i, cnt+1, pick);
            check[i]=false;
        }
    }
    
    public boolean isPossible(){
        int cnt=0;
        for (int i=0; i<check.length-1; i++){
            if (check[i]){
                cnt+=win[i];
            }
        }
        if (cnt<=N){
            nums=cnt;
            return true;
        }
        else{
            return false;
        }
    }
    
    public void calc(){
        int ryan_score=0;
        int apeach_score=0;
        for (int i=0; i<10; i++){
            if (check[i]){
                ryan_score+=(10-i);
            }
            else if (sinfo[i]!=0){
                apeach_score+=(10-i);
            }
        }
       if (max<=(ryan_score-apeach_score)){
           int temp[]=new int[11];
           for (int i=0; i<10; i++){
               if (check[i]){
                   temp[i]=win[i];
               }
               else{
                   temp[i]=0;
               }
           }
           temp[10]=N-nums;
           if (max==(ryan_score-apeach_score)){
                for (int i=10; i>=0; i--){
                    if (temp[i]==answer[i]){
                        continue;
                    }
                    else if (temp[i]>answer[i]){
                        answer=temp;
                        break;
                    }
                    else{
                        break;
                    }
                }
           }
           else{
               max=ryan_score-apeach_score;
               answer=temp;
           }
       }
    }
}

나의 풀이:

 

1점~10점 중 라이언이 이길 점수를 고른다=>계산하여 max 값 구한다 

조합을 이용해서, 10C1, 10C2 ... 10C10 조합을 모두 구한다. (이때 고르는 것은 라이언이 이길 점수)

구한 조합에서 라이언이 쏠 수 있는 화살의 수를 초과하지 않았는지 체크한후,

초과하지 않았으면 각 점수를 계산해서 최대값을 구하는 방식이다. 

처음엔 0점을 얻는 경우도 조합에 포함시켜서 오답이었다. 0점을 얻는 경우는 제외하고 이길 수 있는 점수의 조합을 구해야된다.

but 구글링 후, 다른분들의 코드를 보고 나니, 나의 코드가 너무 길고, dfs 탐색으로 간단하게 해결할 수 있다는 사실을 알았다..

 

라이언은 어피치보다 하나 더 맞추거나 & 아님 아예 안맞추던가 2가지 선택을 해야 한다.

이건 내 코드 발상과 동일했으나, dfs 로 간단하게 해결하는 방법을 몰랐다..

 

아래는 dfs 재귀를 이용해 다시 푼 코드.

import java.util.Arrays;

class Solution {
    static final int N=11;
    static int max=0;
    static int chance;
    static int[] answer;
    public int[] solution(int n, int[] info) {
        chance=n;
        int[] ryan=new int[N];
        dfs(info, ryan, 0, 0);
        if (max==0){
            answer=new int[]{-1};
        }
        return answer;
    }
    public int getScore(int[] apeach, int[] ryan){
        int ascore=0;
        int rscore=0;
        for (int i=0; i<N; i++){
            if (apeach[i]==0 && ryan[i]==0){
                continue;
            }
            if (apeach[i]<ryan[i]){
                rscore+=(10-i);
            }
            else{
                ascore+=(10-i);
            } 
        }
        return rscore-ascore;
    }
    
    public boolean compares(int[] ryan, int[] answer){
        for (int i=N-1; i>=0; i--){
            if (ryan[i]>answer[i]){
                return true;
            }
            else if (ryan[i]<answer[i]){
                return false;
            }
        }
        return false;
    }
    
    public void dfs(int[] apeach, int[] ryan, int cnt, int idx){
        if (cnt==chance || idx==N){
            boolean flag=false;
            int score=getScore(apeach,ryan);
            if (score>0){
                if (cnt<chance){
                    ryan[idx-1]+=(chance-cnt);
                    flag=true;
                }
                if (max<score){
                    answer=Arrays.copyOf(ryan,N);
                    max=score;
                }
                else if (max==score && compares(ryan,answer)){
                    answer=Arrays.copyOf(ryan,N);
                }
            }
            if (flag){
                ryan[idx-1]-=(chance-cnt);
            }
            return;
        }
        if (chance-cnt>apeach[idx]){
            ryan[idx]=apeach[idx]+1;
            dfs(apeach, ryan, cnt+ryan[idx], idx+1);
            ryan[idx]=0;
        }
        dfs(apeach, ryan, cnt, idx+1);
    }
}

dfs 2가지 경우의 수 존재한다. 이 경우의 수를 계속 탐색해간다.

종료조건은 남은 화살의 개수가 없을 때, 혹은 다 쐈을 때이다. 이때 점수를 계산한 뒤,

라이언이 이기는 경우에 한해 아직 남은 화살이 있을 경우 0점에 모두 몰아넣어준다. (가장 낮은 점수를 많이 맞출경우 우선순위가 높다는 조건이 있으므로), max값을 비교해 max 값과 점수가 같을 경우에는 그 둘을 비교해줘서 우선순위 높은 answer을 골라내면 된다.