[Algorithm] 프로그래머스 - 양궁대회 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 - 양궁대회 자바 풀이를 작성하고자 합니다.

 

문제 출처:  https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

 

 

 

1. 풀이 소스

 

class Solution {

    int[] lion; // 라이언 점수
    int[] answer; // 정답을 복사할 배열
    int max = -1; // 최대값

    public int[] solution(int n, int[] info) {
        lion = new int[11];
        answer = new int[11];

        dfs(0, n, info);

        if (max == -1) return new int[]{-1}; // 경우의 수가 없는 경우 리턴

        return answer;
    }

    private void dfs(int depth, int n, int[] apeach) {
        if (depth == n) {
            int score = calculate(apeach); 
            if (max <= score) { // 참고 #1
                max = score; // 최대값 업데이트
                answer = lion.clone(); // lion의 배열의 값을 복사, 참조로 할 경우 lion이 바뀌면서 값이 바뀜
            }
            return;
        }

        // lion[i] <= apeach[i] 조건 (apeach의 10점을 3번 맞췄다면, lion은 10점을 얻으려면 4번을 맞춰야함)
        for (int i = 0; i < apeach.length && lion[i] <= apeach[i]; i++) {
            lion[i] += 1; // 해당 인덱스에 1 증가 -> 다음 dfs에서도 1 증가할 수 있음 따라서 위의 조건까지 반복
            dfs(depth + 1, n, apeach); 
            lion[i] -= 1; // 위에서 추가한 lion 배열에서 1을 감소하는 작업을 모든 dfs에서 수행하므로 원점 복구 가능
        }
    }

    int calculate(int[] apeach) {
        int apeachScore = 0;
        int lionScore = 0;

        for (int i = 0; i < lion.length; i++) {
            if (apeach[i] == 0 && lion[i] == 0) continue;
            if (apeach[i] >= lion[i]) apeachScore += (10 - i); 
            else lionScore += (10 - i);
        }

        if (apeachScore <= lionScore) return lionScore - apeachScore;
        return -1;
    }
    
    /*
    # 참고1
    해당 로직에서 스코어가 같으면 가장 작은 점수를 더 많이 맞춘 배열을 체크하지 않고 업데이트 하는 이유
    하단에 for문을 보면, i++로 상향식 반복문이 진행
    따라서, 가장 최근에 업데이트 되는 score는 가장 적은 점수의 과녁을 더 많이 맞춘 배열
    */
}

 

 

 

2. 문제 풀이 과정

 

해당 문제는 dfs로 해결해야 하는 문제입니다. 처음 풀이하는 과정에, 더 큰 점수 차이를 기록한 배열들이 여러 개인 경우 어떻게 차이를 구분해야 하는가에 대한 고민을 하였습니다.

 

이 과정에서, 주석 처리한 참고1을 확인하면 해당 문제를 해결할 수 있습니다.

상향식으로 반복문을 돌다보면, i++로 인해 배열의 끝에 있는 i를 업데이트하게 됩니다.

만약 더 큰 점수차이가 여러 개이더라도 더 적은 과녁을 하나라도 더 맞힌 배열을 리턴하게 됩니다. 

 

lion[i] += 1;

dfs()

lion[i] -= 1;

 

이 로직은, i 번째 과녁을 선택하지 않을 수 있습니다. 이 경우, 다음 인덱스로 넘겨주기 위해 재귀 성질을 이용하여 더한 만큼 다시 빼주면 원점으로 돌릴 수 있습니다.

 

자세한 풀이 과정은 마찬가지로 소스에 주석 처리하였습니다.

이상으로 프로그래머스 양궁대회 풀이를 마치겠습니다. 감사합니다.