프로그래머스 - 양궁대회 [Java]

이 문제는 백트래킹을 이용해서 푸는 문제이다.

 

처음에는 이 문제를 풀 때 apeech 보다 1 많은 화살로 한번에 빼는 방식으로 풀었으나 오답이 나왔다.

그래서 검색을 통해 그냥 백트래킹을 이용하는 것이 구현도 직관적이고 풀이도 쉽다는 사실을 발견했다.

 

처음 풀었던 방식의 문제점은 화살이 남는 경우에 대해 로직이 모호하다는 것이다. 마지막까지 도달했을 때 남은 화살을 전부 0점에 꽂아넣는 방식으로 구현했으나 오답이었다.

 

그냥 백트래킹은 당연히 시간 초과가 나기 때문에, 여러 가지 장치를 해주면 시간 안에 풀 수 있다.

먼저 start 매개변수를 두어 순서가 뒤바뀐 똑같은 결과를 만들지 않도록 순서를 강제한다.

그 다음 apeech보다 1만 많으면 되므로, ryan이 이미 화살이 더 많은 경우에는 continue로 재귀 호출을 하지 않게 만들면 된다.

import java.util.*;

class Solution {
    int[] apeech;
    static final int END = 11;
    
    int dist = -1;
    int[] result = null;
    
    public int[] solution(int n, int[] info) {
        apeech = info;
    
        int[] ryan = new int[END];
        
        solve(ryan, n, 0, 0);
    
        if (result == null) {
            int[] answer = {-1};
            return answer;
        }
        
        return result;
    }
    
    void solve(final int[] ryan, final int max, final int cnt, final int start) {
        if (cnt == max) {
            if (isRyanWin(ryan)) {
                final int[] temp = copy(ryan);
                final int currentDist = calculateDist(temp);
                
                if (result == null) {
                    dist = currentDist;
                    result = temp;
                    
                    return;
                }
                
                if (dist < currentDist) {
                    dist = currentDist;
                    result = temp;
                    
                    return;
                }
                
                if (dist == currentDist) {
                    result = compare(result, temp);
                }
            }
            
            return;
        }
        
        for (int i = start; i < END; i++) {
            if (ryan[i] > apeech[i]) {
                continue;
            }
            
            ryan[i]++;
            solve(ryan, max, cnt + 1, i);
            ryan[i]--;
        }
    }
    
    int[] copy(final int[] ryan) {
        int[] result = new int[END];
        
        for (int i = 0; i < END; i++) {
            result[i] = ryan[i];
        }
        
        return result;
    }
    
    int[] compare(final int[] left, final int[] right) {
        for (int i = END - 1; i >= 0; i--) {
            if (left[i] > right[i]) {
                return left;
            } else if (left[i] < right[i]) {
                return right;
            }
        }
            
        return left;
    }
    
    int calculateDist(final int[] ryan) {
        int apeechScore = 0;
        int ryanScore = 0;
        
        for (int i = 0; i < END; i++) {
            final int score = 10 - i;
            
            if (apeech[i] == 0 && ryan[i] == 0) {
                continue;
            }
            
            if (apeech[i] < ryan[i]) {
                ryanScore += score;
            } else {
                apeechScore += score;
            }
        }
        
        return ryanScore - apeechScore;
    }
    
    boolean isRyanWin(final int[] ryan) {
        int apeechScore = 0;
        int ryanScore = 0;
        
        for (int i = 0; i < END; i++) {
            final int score = 10 - i;
            
            if (apeech[i] == 0 && ryan[i] == 0) {
                continue;
            }
            
            if (apeech[i] < ryan[i]) {
                ryanScore += score;
            } else {
                apeechScore += score;
            }
        }
        
        if (ryanScore > apeechScore) {
            return true;
        }
        
        return false;
    }
}