[프로그래머스,Java] Level2:양궁대회

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

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

 

문제가 길어 링크로 대체합니다.

 

 

문제분석:

 

목표: 라이언과 어피치의 과녁점수가 최대일때 맞춘 과녁의 점수판을 반환해주세요.

 

 

특수조건:

1. 라이언과 어피치가 동점일경우, 어피치의 승리입니다.

2. 어피치가 승리할경우 -1을 반환

3. 만약, 과녁점수가 동일한기록이 여러개 존재할경우, 낮은 점수를 많이 맞힌것을 정답으로합니다.

 

 

이 문제가 정말 어렵다고 느끼게하는건 바로 3번때문일겁니다.

 

라이언 - 어피치 점수가 최대인 기록이 여러개있다면, 그중에서 낮은점수를 많이 맞힌걸 뽑아야합니다.

 

그래서 어쩔수없이 완전탐색을 돌려야합니다.

전 백트래킹을 사용하여 완전탐색을 돌렷습니다.

 

우선 전역변수입니다. 백트래킹을 깔끔하게 돌리기위해서 미리 선언해뒀습니다.

화살의 점수는 0~10점이니 11개의 배열을 만들어줍니다.

 

visited는  그 점수를 먹었는지 안먹었는지 확인하는용도

total은  어피치가 먼저 기록을낸 점수의 합계

max는   라이언 - 어피치의 최대 점수차

need 는  해당 점수를 먹기위해 화살을 몇발 투자해야하는지를 저장하는 배열입니다.

vict는  victory의 약자로,  최종적으로 반환할 답안입니다.

 

메인함수부분입니다. need[]의 배열을 채워주는데

 

need는 어피치가 투자한 화살 +1만큼 투자하면 그 점수를 얻을수 있다는 뜻입니다.

그리고 need[10]을 0으로 다시 설정한 이유는, 투자를하던 안하던 0점을 얻을수 있기때문입니다. 

 

그리고 rec() 백트래킹을 실행합니다.

 

이 결과로 max==0 즉, 어피치와 라이언이 동점일경우 -1을 반환합니다.

 

 

백트래킹 부분입니다. 

 

우선 화살을 먹을때의 조건을 n>=need[i] 즉,  X점 화살을 먹기위한 화살이 충분한가?를

따져줍니다.

 

그 후, 백트래킹의 기본인  visited 방문체크를합니다.

방문 체크를하였으니,  사용한 화살도 빼줍니다. n-=need[i]

 

그리고 rec(start+1,r-1,n) 으로 재귀를 돌립니다. 

 

재귀를 돌렸다면 방문체크를 해재하고 화살도 다시 더해줍니다.

 

 

그리고 아주 중요한 탈출조건입니다.

 

보통 탈출조건은 1개인데 이번 문제는 탈출조건이 2개정도 필요한것같습니다.

if(n==0){
            int sum=0;
            int[] arr = new int[11];
            for(int i=0;i<11;i++){
                if(visited[i]){               
                    arr[i]=need[i];
                    if(arr[i]==1){
                        sum+=10-i;
                    }
                    else{
                        sum+=(10-i)*2;
                    }
                }              
            }
            if(max==sum-total){
                for(int i=10;i>=0;i--){
                    if(vict[i]>arr[i]){
                        break;
                    }
                    else if(vict[i]==arr[i]){
                        continue;
                    }
                    else{
                        vict=arr;
                    }
                }
            }
            else if(max<sum-total){
               max=Math.max(sum-total,max);
               vict=arr;
            }
            return;
        }

15~31줄은 라이언-어피치인 max를 갱신하는 로직입니다.

특히 if(max==sum-total)일때, 최고점수가 같을때  0점화살부터 비교하여 화살이 많은걸 우승후보로 설정합니다.

if(r==0){
            int sum=0;
            int[] arr = new int[11];
            for(int i=0;i<11;i++){
                if(visited[i]){               
                    arr[i]=need[i];
                    if(arr[i]==1){
                        sum+=10-i;
                    }
                    else{
                        sum+=(10-i)*2;
                    }
                }              
            }
            arr[10]=n;
            if(max==sum-total){
                for(int i=10;i>=0;i--){
                    if(vict[i]>arr[i]){
                        break;
                    }
                    else if(vict[i]==arr[i]){
                        continue;
                    }
                    else{
                        vict=arr;
                    }
                }
            }
            else if(max<sum-total){
               max=Math.max(sum-total,max);
               vict=arr;
            }
            return;
        }

문제풀이:

class Solution {
 
boolean[] visited = new boolean[11];
int total=0;
int max=0;
int[] need= new int[11];
int[] vict= new int[11];
 
    public int[] solution(int n, int[] info) {
        int[] answer = {};
        for(int i=0;i<11;i++){
            need[i]=info[i]+1;
            if(info[i]!=0){
                total+=10-i;
            }
        }
        need[10]=0;
        rec(0,11,n);    
        if(max==0){
            return new int[]{-1};
        }
        return vict;
    }
 
    public void rec(int start,int r,int n){
        if(r==0){
            int sum=0;
            int[] arr = new int[11];
            for(int i=0;i<11;i++){
                if(visited[i]){               
                    arr[i]=need[i];
                    if(arr[i]==1){
                        sum+=10-i;
                    }
                    else{
                        sum+=(10-i)*2;
                    }
                }              
            }
            arr[10]=n;
            if(max==sum-total){
                for(int i=10;i>=0;i--){
                    if(vict[i]>arr[i]){
                        break;
                    }
                    else if(vict[i]==arr[i]){
                        continue;
                    }
                    else{
                        vict=arr;
                    }
                }
            }
            else if(max<sum-total){
               max=Math.max(sum-total,max);
               vict=arr;
            }
            return;
        }
        if(n==0){
            int sum=0;
            int[] arr = new int[11];
            for(int i=0;i<11;i++){
                if(visited[i]){               
                    arr[i]=need[i];
                    if(arr[i]==1){
                        sum+=10-i;
                    }
                    else{
                        sum+=(10-i)*2;
                    }
                }              
            }
            if(max==sum-total){
                for(int i=10;i>=0;i--){
                    if(vict[i]>arr[i]){
                        break;
                    }
                    else if(vict[i]==arr[i]){
                        continue;
                    }
                    else{
                        vict=arr;
                    }
                }
            }
            else if(max<sum-total){
               max=Math.max(sum-total,max);
               vict=arr;
            }
            return;
        }
        
        for(int i=start;i<11;i++){
            if(n>=need[i]){
            visited[i]=true;
            n-=need[i];
            rec(start+1,r-1,n);
            visited[i]=false;
            n+=need[i];
            }
 
        }   
    }
}