프로그래머스 - 양궁대회

문제

https://www.acmicpc.net/problem/92342

풀이

• n개의 화살을 날렸을 때 맞출 수 있는 과녁들의 경우의 수를 중복 조합을 이용해서 구한다
• 각 경우에 대해 점수를 계산하고 라이언이 승리하는 경우 해당 경우(배열)을 리스트에 삽입한다
• 모든 경우를 계산하고 리스트를 문제 조건에 맞게 정렬하고, 가장 첫번째 원소를 출력한다

유의할 점

• 중복 조합을 구하는데 코드를 바로 작성하지 못했다. 순열, 조합과 관련된 코드는 바로 짤 수 있도록 연습이 필요
• 리스트를 정렬하는데 점수 차이가 아닌, 라이언이 낼 수 있는 최고 점수로 계산하여 시간을 크게 낭비했다.

코드

import java.util.*; 
class Solution {
    static int[] points = new int[11]; 
    static int count =0; 
    static int[] inf; 
    static int max =0; 
    static List<int[]> list = new LinkedList<>();

    public int[] solution(int n, int[] info) {
        count =n; 
        int[] answer = {};
        inf = info; 
        dfs(0,0);
        
        Collections.sort(list, (o1,o2)->{
        int sum1=0, sum2=0; 
            int in1=0, in2=0; 
        for(int i=0; i<11; i++) {
            if(o1[i]>inf[i]) sum1+= 10-i; 
            else if(o1[i]<=inf[i]&& inf[i]!=0) in1+=10-i; 
            if(o2[i]>inf[i]) sum2+=10-i;
            else if(o2[i]<=inf[i]&& inf[i]!=0) in2+=10-i; 
        }
        if(sum1-in1==sum2-in2)
        for(int i=10; i>=0; i--) {
            if(o2[i]== o1[i])continue; 
            return o2[i] -o1[i];
        }
        return (sum2-in2)-(sum1-in1);
    });
        if(list.size()>0)return list.get(0);
        else return new int[]{-1};
    }
    
    public void dfs(int len, int index){
        if(len == count){
            int p1 =0;
            int p2 = 0 ;
            for(int i=0; i<11; i++){
                if(inf[i]<points[i]) p2+=10-i;
                else if(inf[i]>points[i]) p1+=10-i; 
                else if(inf[i]==points[i] && inf[i]!=0) p1+=10-i;
            }
            if(p2>p1) {
                list.add(points.clone()); 
            }
            return ;
        }
        for(int i=index; i<11; i++){
            points[i]++; 
            dfs(len+1,i);
            points[i]--; 
        }
    }
}