[Programmers] 양궁대회 (카카오 2022 공채)

[문제 링크]

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

프로그래머스

 

 

[코드]

class Solution {
    // 가장 많은 차이로 이기는 경우
    private int maxDiff = -1;
    // 조건에 가장 알맞는 최고의 정답
    private int[] bestAnswer = {-1};
    
    // 위 두개는 일단 모든 경우를 해도 라이언이 이길 수 없는 경우일때의 정답으로 초기화
    
    public int[] solution(int n, int[] info) {
        
        // 라이언의 info
        int[] ryan = new int[11];
        
        // 백트래킹 시작
        // (어피치 info, 라이언 info, guswo 바라보고 있는 idx, 화살의 갯수)
        backtracking(info, ryan, 0, n);
        
        return bestAnswer;
    }
    
    public void backtracking(int[] aPeach, int[] ryan, int idx, int arrows) {
        
        // 종료 조건 설정
        // 현재 바라보고 있는 idx가 마지막 0점 과녁 idx 이거나
        // 쏠 수 있는 화살이 없을때
        if(idx == 11 || arrows == 0) {
            // 남은 화살이 있으면 0점에 모두 배치
            if (arrows > 0) {
                ryan[10] = arrows;
            }
            
            // 점수 계산
            int aPeachScore = 0;
            int ryanScore = 0;
            
            for(int i = 0; i < 11; i++) {
                if(aPeach[i] > ryan[i]) {
                    aPeachScore += 10 - i;
                }
                
                if(aPeach[i] < ryan[i]) {
                    ryanScore += 10 - i;
                }
            }
            
            // 라이언 점수가 어피지 점수보다 클 때
            if(ryanScore > aPeachScore) {
                // 점수 차이
                int diff = ryanScore - aPeachScore;
                
                
                // 점수 차이가 기존 maxDiff보다 크고
                // 문제의 조건에 점수 차이가 같으면 작은 점수를 많이 가진 것이 더 bestAnswer
                // isLowerScore로 bestAnswer과 현재 라이언 info를 비교
                if(maxDiff < diff || (diff == maxDiff && isLowerScore(ryan))) {
                    
                    // clone 중요 !!!!
                    // 안하면 bestAnswer이 ryan 배열을 바라보고 있기 때문에
                    // ryan 배열이 변경되면 같이 변경
                    bestAnswer = ryan.clone();
                    maxDiff = diff;
                }
            }
            
            // 백트래킹 -> 0점에 넣었던 화살 제거
            // 화살을 다 써서 앞에 if 문을 탄게 아니라면
            if (arrows > 0) {
                ryan[10] = 0;
            }
            
            return;
        }
        
        // 선택1: 현재 점수를 포기하고 다음 점수로 이동
        backtracking(aPeach, ryan, idx + 1, arrows);
        
        // 선택2: 현재 점수를 가져감
        // 그러기 위해선 어피치가 이번 점수에서 쏜 화살보다 하나 더 쏴야함
        int needed = aPeach[idx] + 1; // 필요한 화살 수
        
        if(arrows >= needed) {
            ryan[idx] = needed;
            // 화살 쏜 만큼 빼 줌
            backtracking(aPeach, ryan, idx + 1, arrows - needed);
            // 백트래킹하고 돌아왔을때 0으로 초기화 해줘야함
            ryan[idx] = 0;
        }
        
    }
    
    public boolean isLowerScore (int[] ryan) {
        for(int i = 10; 0 <= i; i--) { 
            if(bestAnswer.length == 1) {
                return true;
            }
            
            if(ryan[i] == bestAnswer[i]) {
                continue;
            }
            
            if(ryan[i] > bestAnswer[i]) {
                return true;
            }
            
            if(ryan[i] < bestAnswer[i]) {
                return false;
            }
        }
        
          return false;
    }
}

[회고]

풀이 과정을 보고 혼자 풀어보았습니다.
백트래킹으로 푸는건 알았지만 백트래킹 알고리즘 구현이 익숙지 않아서

애를 많이 먹었습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.