접근

양궁대회

틀린 풀이

저의 잘못된 접근 방법은 아래와 같습니다.

1. DFS와 백트래킹을 이용해서 라이언이 쏠 수 있는 모든 경우의 수를 만든다.
2. 단, DFS가 시간초과가 발생할 수 있으므로 Set을 이용해서 중복된 조합이 Set에 존재하는 경우 DFS의 재귀호출이 발생하지 않도록 합니다.
   -여기서 Set에 배열을 저장하는 경우 같은 배열에 대해서 같다고 인식하지 못합니다.
   -그래서 ArrayList를 넣었습니다.
3. n개의 과녁을 모두 쏜 경우 DFS의 재귀호출을 멈추며
4. 문제에 주어진 어피치의 점수와 비교해서 그 점수보다 크고
5. max(초기값은 Integer.MIN_VALUE)보다 크면
6. bigStore이라는 ArrayList에 라이언의 과녁(arrow라는 List)을 저장합니다
7. 위 조건에 따라 모든 경우의 수를 만들었다면
8. bigStore에 저장된 ArrayList 중에서 max와 같은 값을 가진 List를 다시 eqScore에 저장합니다.
9. 그리고 eqScore를 정렬해야 하는데 eqScore은 2차원 ArrayList이기 때문에 정렬하기가 어려웠습니다.

import java.util.*;

class Solution {


    static int max = Integer.MIN_VALUE;

    static class Arrow{
        boolean tag;
        List<Integer> list;
        int score;
        public Arrow( List<Integer> list, int score, boolean tag){
            this.list = list;
            this.score = score;
            this.tag =tag;
        }
    }

    static ArrayList<Arrow> bigStore = new ArrayList<Arrow>();
    static int[] inFo;
    static Set< List<Integer> > set = new HashSet<>();

    public List<Integer> solution(int n, int[] info) {

        List<Integer> answer = new ArrayList<>();

        // 라이언 저버 양궁대회 우승자 VS. 어피치
        //1. 어피치가 화살 n발 -> 라이언 화살 n발
        //2. 점수 계산
        // k점을 어피치가 a발, 라이언 b발
        // 더 많은 발을 맞춘 선수가 k점을 획득
        // 단 a=b인 경우 어피치가
        // 단 a=b=0인 경우 누구도 가져가지 못함
        //3. 최종 점수가 큰 사람 우승, 단 같은 경우 어피치가 우승자

        // 어피치가 n발을 다 쏘고 -> 라이언이 쏠 차례이며 큰 점수차로 우승하고 싶다
        // 화살 개수 n, 어피치의 10~0점 순서대로 과녁 개수를 담은 배열 info
        // 라이언의 어떤 점수의 과녁에 발-> return 
        // 우승할 방법이 여려 -> 가장 낮은 점수를 더 많이 맞힌 경우 return
        // 무조건 지거나 비기는 경우-1



        inFo = info;

        List<Integer> list = new ArrayList<>();
        for(int i=0;i<11;i++){
            list.add(0);
        }
        dfs(n,list);


        if(bigStore.size()==0){
            answer.add(-1);
            return answer;
        }

        ArrayList<ArrayList<Integer>> eqScore = new ArrayList<>();

        for(Arrow a : bigStore){
            if(a.score==max){
                eqScore.add(new ArrayList<>(a.list));
            }
        }


      
        int cnt=0;
        for(int j=10;j>=0;j--){
           int compare=0;
            boolean tag = false;
           for(int i=0;i<eqScore.size();i++){
               int index = eqScore.get(i).get(j);
               if(index!=0 && compare<=index){
                   if(compare==index) tag=true;
                   answer = eqScore.get(i);
                   compare = index;
               }
               System.out.println(i+":"+j+":"+index+":"+compare);
           }
           if(cnt==1) break;
       }

        return answer;
    }
    static void dfs(int n, List<Integer> arrow){
        if(n==0){
            Arrow result = check(inFo, arrow);
          
            // rion이 우승하는가?
            if(result.tag && max<=result.score){
                bigStore.add(new Arrow(new ArrayList<>(result.list),result.score,result.tag));
                max = result.score;
             

            }
            return;
        }else{
            for(int i=0;i<11;i++){
                arrow.set(i,arrow.get(i)+1);
                if(!set.contains(arrow)){
                    set.add(arrow);
                    dfs(n-1,arrow);
                }
                arrow.set(i,arrow.get(i)-1);
            }

        }
    }

    // 라이언과 어피치의 점수를 비교하는 메서드
    static Arrow check(int[] inFo, List<Integer> arrow){

        int peach=0;
        int rion=0;

        for(int i=0;i<11;i++){
            if(inFo[i]==arrow.get(i)){
               if(inFo[i]!=0) peach+=(10-i);
            }else if(inFo[i]>arrow.get(i)){
                peach+=(10-i);
            }else{
                rion+=(10-i);
            }
        }

        //System.out.println(rion+","+peach+","+arrow);
        if(peach>=rion){
            Arrow result = new Arrow(arrow,rion,false);
            return result;
        }else{
            Arrow result = new Arrow(arrow,rion,true);
            return result;
        }



    }
}

정답 풀이

이 풀이의 전제조건은 간단합니다.
DFS와 백트래킹을 이용해서 풀지만
모든 경우의 수를 만들 필요가 없다는 것입니다.

그 이유는 어피치가 쏜 과녁보다 하나만 더 많이 쏘면 어차피 그 점수를 얻게되기 때문에 해당 과녁의 화살 수가 어피치의 과녁 수보다 하나더 크면 재귀호출을 멈추어 화살을 아끼게 됩니다.

public class Solution {
	static private int[] res = new int[11];//점수차가 최대일때 라이언이 쏜 화살배열
	static private int[] lion= {-1};//정답배열
	static private int max = Integer.MIN_VALUE;//최대값
    public static int[] solution(int n, int[] info) {
        back(0,n,info);//라이언이 쏜 화살에 대한 조합
        
        if(max==-1) {//라이언이 어피치를 못 이길떄
        	lion = new int[1];
        	lion[0]=-1;
        }
        return lion;
    }
    
    public static void back(int depth, int n, int[] info) {
    	//화살 다 꽂았을때(종료조건)
    	if(depth==n) {
    		int diff = score(info);//점수차 구하기
    		if(max<=diff) {//점수차 최대값 갱신
    			max = diff;
                for(int i=0;i<11;i++)
                    System.out.print(res[i] +" ");
                System.out.println();
    			lion = res.clone();
    		}
    		return;
    	}
    	
    	//res[i]<=info[i] -> i과녁에 라이언이 화살을 더 많이 맞추면 반복문 종료한다.
    	for(int i=0; i<info.length && res[i]<=info[i]; i++) {
    		res[i] += 1;
    		back(depth+1, n, info);
    		res[i] -= 1;
    	}
    }
    
    //점수차 구하기
    public static int score(int[] info) {
    	int apeach=0, lion=0;
    	for(int i=0; i<res.length; i++) {
    		if(info[i]==0 && res[i]==0) continue;//i원소에 둘다 0개 맞췄을땐 무시.
    		if(info[i]>=res[i]) apeach += (10-i);
    		else lion += (10-i);
    	}
    	
    	int diff = lion - apeach;
    	if(diff<=0) return -1;
    	return diff;
    }
}