2022 KAKAO BLIND RECRUITMENT - 양궁대회 (JAVA)

❓ 문제 - 2022 KAKAO BLIND RECRUITMENT 양궁대회 - JAVA 풀이법

출처 

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

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

 

 

 

📝 문제해결법 

1. DFS를 통해 완전탐색하여 해결하였다.

• info의 길이가 최대 11이고, n이 최대 10이므로 완전탐색을 통해 라이언이 과녁을 맞힌 갯수를 모두 완전탐색한다.
• dfs를 통해 10(idx=0) ~ 0(idx=10)점을 맞춘 경우를 완전탐색하고 기저조건인 depth가 N(화살의 개수)일 때 10점부터 1점까지 어피치가 맞은 화살갯수와 라이언이 맞춘 화살 갯수를 비교해서 조건에 따라 각 화살 점수를 누가 가져갈지 따진다.
• 조건에서 둘다 k점수에 대해 0개 0개 쏜 경우는 둘 다 0점이고, 만약 어피치가 라이언의 이상만큼 쏜 경우는 k점수를 어피치가 가져가고 라이언이 어피치가 맞춘 갯수를 초과해서 맞췄을 땐 라이언이 k점수를 획득한다.
• 총 합에서 만약 라이언이 어피치의 총합 점수를 초과해서 얻은 경우는 둘의 총합 차이 diff를 계산해서 최대 차이(max_diff)를 계속 갱신한다.
• 만약 max_diff가 갱신되었을 때는 기존 list를 clear 해준 뒤 list에 해당 라이언의 과녁을 맞춘 배열을 add하고, max_diff와 diff가 같다면 라이언이 과녁을 맞춘 배열을 list에 add해준다.
• DFS 탐색을 끝난 뒤 만약 라이언이 어피치보다 총합이 더 크게 난 경우가 없다면 new int[]{-1}을 리턴한다.
• 만약 라이언이 가장 큰 차이 점수 차이로 우승할 수 있는 방법이 여러가지인 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해야하므로 람다식 문법을 활용해서 가장 낮은 점수가 더 많은 경우로 리턴하도록 구현한다.

 

2. 느낀점

• DFS로 완전탐색을 하는 것과 어떤 람다식의 조건으로 정렬을 해서 푸는 것은 감이 왔는데.. 평소에 정렬에 조건을 활용할 때 Comparable<T>만 사용해서.. 방법을 몰랐다.
• 다행이 이 부분은 구글링 서치를 통해 배웠고 적용시켰다.
• 처음에 람다식 부분에 생각없이 o1[i] - o2[i]로 순서를 바꿔서 구현했는데 틀려서.. 더 생각해보니, 문제에서는 가장 낮은 점수를 더 많이 맞힌 경우(-> 내림차순 정렬 필요) 하므로 o2[i] - o1[i] 순서로 바꿔서 구현해야한다고 더 배웠다.

 

💻 소스코드 

// 2022 KAKAO BLIND RECRUITMENT - 양궁대회
// DFS

import java.util.*;

class Solution {
    public static ArrayList<int[]> list = new ArrayList<int[]>();
    public static int max_diff = -1;
    public static int[] ryan;
    public static int[] apeach;
    
    public int[] solution(int n, int[] info) {
        int[] answer = {};
        ryan = new int[11];
        apeach = info;
        
        dfs(n, 0, 0);
        if(max_diff == -1) return new int[]{-1};
        
        Collections.sort(list, (o1, o2) -> {
           for(int i=10;i>=0;i--){
               if(o1[i] != o2[i]) return o2[i] - o1[i];
           } 
           return 0;
        });
        
        return list.get(0);
    }
    
    public static void dfs(int n, int depth, int start){
        if(depth == n){
            int a_sum = 0;
            int r_sum = 0;
            for(int i=0;i<10;i++){
                if(apeach[i] == 0 && ryan[i] == 0) continue;
                if(apeach[i] >= ryan[i]) a_sum += (10-i);
                else r_sum += (10-i);
            }
            
            if(r_sum > a_sum){
                int diff = r_sum - a_sum;
                if(max_diff < diff){
                    max_diff = diff;
                    list.clear();
                    list.add(ryan.clone());
                } else if(max_diff == diff){
                    list.add(ryan.clone());
                }
            }
            
            return;
        }
        
        for(int i=start;i<11;i++){
            ryan[i]++;
            dfs(n, depth+1, i);
            ryan[i]--;
        }
    }
}