[프로그래머스] 양궁대회 (JAVA 풀이)

 

문제 접근

 

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

프로그래머스

 

쏠 수 있는 화살의 점수가 0~11점까지라 완전 탐색으로 접근하면 풀 수 있을 것이라고 생각했지만 재귀 구현이 약해서 그런지 구현에 어려움을 느꼈던 문제였다.

 

문제 풀이

 

우선 총 3개의 함수로 나눠서 구현하는걸 목표로 잡고 시작했다.

 

1. 라이언과 어피치의 점수 차이를 반환하는 함수

 

2. 정답 배열 중에 누가 우선순위가 높은지를 반환하는 함수

 

3. 재귀를 통해 모든 경우를 탐색하는 함수

 

 

라이언과 어피치의 점수 차이를 반환하는 함수는 문제 그대로 특정 점수의 과녁에 대해 어피치가 라이언과 같거나 더 많이 맞췄으면 어피치가 점수를 획득하니까 차이를 나타내는 diff 변수에서 해당 과녁의 점수 만큼을 빼줬고 라이언이 점수를 획득한 경우는 더해줬다.

 

---

 

정답 배열의 우선순위를 알려주는 함수는 문제의 조건대로 배열의 뒤에서부터 (더 낮은 점수 부터) 동일한 화살을 쐈다면 넘어가고 만약 다른 개수의 화살을 맞췄다면 비교하는 배열이 더 낮은 점수에서 화살을 많이 맞췄는지 여부를 반환해준다.

---

 

이제 재귀를 통해 모든 경우를 탐색하는 함수인데 이 부분이 가장 어려웠음

우선 가장 큰 점수 차이를 기록하기위해 max 변수와 그 때의 맞힌 과녁 점수의 개수를 담을 maxArr 배열을 선언했다

 

---

 

전체적인 흐름은 0번 인덱스(10점 과녁)부터 10번 인덱스(0점 과녁)까지 라이언이 어피치를 이기기 위해 필요한 화살 (어피치가 해당 과녁의 쏜 화살 개수의 + 1)을 라이언이 남은 화살로 쏠 수 있다면 해당 과녁에서 어피치를 이기는 경우와 해당 과녁의 점수를 포기하는 경우로 나눠서 탐색이 진행됨

 

=> 어피치를 이기기 위해 필요한 화살을 구해주고 남은 화살 n이 충분하다면 현재 과녁(idx 값)에 해당 화살을 꽂아줌, 그리고 idx를 1 증가시켜 다음 과녁에 대한 2가지 상태(어피치를 이기기위한 만큼의 화살을 꽂음, 해당 과녁을 포기함)를 재귀로 호출함 

 

=> 이때, 해당 경우의 수(어피치를 이기기 위한 만큼의 화살을 현재 idx 과녁에 꽂음)로 분기를 시켰다면 (현재 과녁에 화살을 꽂고 재귀를 호출했다면) 현재 idx에 쐈던 화살을 hits[idx] = 0으로 초기화 시켜줘야 현재 과녁을 포기하는 경우도 확인할 수 있음

 

(현재 과녁을 포기하는 경우는 idx를 1 증가시켜주고 hits와 n을 건들지 않고 바로 재귀 호출을함)

 

---

 

종료조건의 경우 만약 현재 idx가 10까지 즉, 0점 과녁까지 도달했다면 남은 화살 개수인 n을 전부 0점 과녁에 쏘는걸로 간주하고 이전에 만들었던 라이언과 어피치의 점수 차이를 반환하는 함수를 사용함

 

=> 이렇게 반환받은 점수 차이가 음수라면 라이언이 우승할 수 없는 경우이므로 따로 max, maxArr을 갱신하지 않고 양수라면 라이언이 우승한 경우일텐데 이 때 저장된 최대 점수 차이보다 큰 경우 max, maxArr을 갱신해준다

 

최대 점수 차이가 동일하다면 이전에 만들었던 배열의 우선순위를 알려주는 함수를 이용해서 만약 갱신이 필요하다면 maxArr을 갱신해준다

=> 최대 점수가 동일하므로 max는 갱신 안해도됨

 

return을 통해 이전 재귀 단계로 돌아가서 다른 경우들을 살펴봐야하므로 hits[10] = 0을 통해  남은 화살들을 0점에 꽂았던 경우를 다시 초기화해줌

 

---

 

만약 위의 재귀가 끝났을 때 max의 값이 처음에 초기화한 Integer.MIN_VALUE라면 갱신되지 않았다는 뜻이므로 라이언이 이길 수 있는 경우가 없는 것임

 

그래서 이 경우는 -1을 배열에 담아 return 해주고 아니라면 maxArr을 반환해주면 끝남

 

전체 코드

 

class Solution {
    
    int[] maxArr = new int[11];
    int max = Integer.MIN_VALUE;

    // lion과 apeach의 점수차이를 반환하는 함수
    int diff(int[] lion, int[] apeach) {
        int diff = 0;
        
        for(int i = 0; i < 11; i++) {
            
            if(apeach[i] == 0 && lion[i] == 0) continue;
            
            if(apeach[i] >= lion[i]) {
                diff -= (10 - i); // 어피치가 점수 획득
            } else {
                diff += (10 - i); // 라이언이 점수 획득
            }
            
        }
        
        return diff;
    }
    
    // 새 배열이 기존 배열보다 우선순위가 높은지를 반환하는 함수
    boolean isPriority(int[] existArr, int[] newArr) {
        for(int i = 10; i >= 0; i--) {
            
            if(existArr[i] == newArr[i]) continue;
            
            return existArr[i] < newArr[i];
        }
        
        return false;
    }
    
    void dfs(int idx, int[] hits, int n, int[] apeach) {
        
        // 0점 과녁(idx=10)까지 탐색을 완료한 경우
        if(idx == 10) {
           
            // 남은 화살(n)은 모두 0점 과녁에 쏘는걸로 간주
            hits[10] = n;
            
            int currentDiff = diff(hits, apeach);
            
            // 라이언이 이긴 경우(diff > 0)에만 결과 갱신
            if(currentDiff > 0) {
                
                // 최대 점수 차이보다 큰 경우
                if(currentDiff > max) {
                    max = currentDiff;
                    maxArr = hits.clone(); // 배열을 복사해서 저장
                } 
                // 최대 점수 차이와 같은 경우는 우선순위 비교
                else if (currentDiff == max && isPriority(maxArr, hits)) {
                    maxArr = hits.clone();
                }
            }
            
            return; 
        }
        
        // 현재 idx의 점수를 '이기는' 경우
        int arrowsNeeded = apeach[idx] + 1; // 이기기 위해 필요한 화살
        if(n >= arrowsNeeded) { // 남은 화살이 충분하면
            hits[idx] = arrowsNeeded;
            dfs(idx + 1, hits, n - arrowsNeeded, apeach);
            hits[idx] = 0; // 쐈던 화살을 0으로 초기화
        }
        
        // 현재 idx의 점수를 포기하는 경우 (0발 쏨)
        dfs(idx + 1, hits, n, apeach); // 다음 점수(idx+1) 탐색
    }
    
    public int[] solution(int n, int[] info) {
        
        dfs(0, new int[11], n, info);
        
        // 탐색이 끝났는데 max가 갱신되지 않았다면 라이언이 이길 수 없는 경우
        if(max == Integer.MIN_VALUE) {
            
            return new int[]{-1};
            
        } else {
            
            return maxArr;
        }
    }
}