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

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

프로그래머스

DFS로 풀 수 있는 문제이다.

 

핵심

n의 크기가 작기 때문에 dfs를 통한 완전탐색을 사용하여 풀 수 있다.

즉 모든 경우의 수를 구하고 그때의 점수를 비교하는 방식으로 풀면 된다.

 

정답 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    private final List<int[]> results = new ArrayList<>();
    private int[] ryan;
    private int maxDiff = 0;
    private int count = 0;

    public int[] solution(int n, int[] info) {
        ryan = new int[11];
        dfs(n, 0, info, 0);

        if (maxDiff == 0) {
            return new int[]{-1};
        }

        results.sort((s1, s2) -> {
            for (int i = 10; i >= 0; i--) {
                if (s1[i] != s2[i]) {
                    return s2[i] - s1[i];
                }
            }
            return 0;
        });

        System.out.println(count);

        return results.get(0);
    }

    private void dfs(int n, int index, int[] info, int start) {
        if (n == index) {
            count++;
            compare(info);
            return;
        }

        for (int i = start; i < 11; i++) {
            ryan[i]++;
            dfs(n, index + 1, info, i);
            ryan[i]--;
        }
    }

    private void compare(int[] info) {
        int ryan_point = 0;
        int apeach_point = 0;

        for (int i = 0; i < 11; i++) {
            if (info[i] == 0 && ryan[i] == 0) {
                continue;
            }
            if (info[i] < ryan[i]) {
                ryan_point += (10 - i);
            } else {
                apeach_point += (10 - i);
            }
        }

        if (ryan_point - apeach_point > maxDiff) {
            results.clear();
            results.add(ryan.clone());
            maxDiff = ryan_point - apeach_point;
        } else if (ryan_point - apeach_point == maxDiff) {
            results.add(ryan.clone());
        }
    }
}

해설

maxDiff는 말 그대로 최대 점수 차이이다. 0으로 설정한 이유는 최선이 비기는 경우(점수가 같은 경우)에도 어피치가 이기는 판정이기에 -1을 리턴하기 위함이다.

다른 부분은 크게 어렵지는 않은데, dfs를 통해서 모든 경우의 수를 구한다. 

ex) 5 0 0 0 0...., 4 1 0 0 0 0......, 4 0 1 0 0..... ,.....  , 0 0 0 0... 0 0 1 총카운트를 세니 184756개가 나온다.

 

각 경우의 수마다 compare를 통해 계산을 진행한다.

점수를 분배하고, 만약 기존 maxDiff보다 ryan의 점수가 높으면 기존 results를 clear 하고 새로운 값을 추가한다.

반대로 이미 동점인 경우 새로운 경우만 추가한다.

 

모든 결과가 나왔다면 sort를 시키는데, 중요한 점은 results의 결과는 모두 같은 점수이므로 가장 낮은 점수를 많이 맞춘 것을 정답으로 채택해한다.

 

 

배운 점

접근 자체는 쉬워서 어렵지는 않았지만, dfs를 최근에 잘 풀지 않아서 생각보다 오래 걸렸다.

요즘에 구현이나 bfs 등등 다른 유형에 재미를 붙여서 소홀히 하였는데, dfs도 종종 풀어야겠다.