프로그래머스 - 양궁대회 JAVA :: 2022 KAKAO BLIND RECRUITMENT :: 92342

문제 링크

코딩테스트 연습 - 양궁대회 | 프로그래머스 스쿨 (programmers.co.kr)

---

문제 이해하기

• 점수는 10~0점까지 11개의 점수가 있습니다.

• 남은 화살의 수가 어피치가 맞힌 화살의 수보다 크지 않으면 그 점수는 무시합니다.
  라이언이 점수를 획득하는 조건은 무조건 어피치보다 많이 맞혀야 하니까요.

이제 예시와 함께 좀 더 자세히 살펴보겠습니다.

화살의 수는 총 5개이며 어피치는 10점(2개), 9점(1개), 8점(1개), 7점(1개) 입니다.

• 어피치의 화살
  

  

  
  기본적으로 10점부터 시작해서 어피치의 점수를 빼앗는 조건 하에 점수차가 가장 많이 나는 조합을 찾는 방법으로 풀었습니다.

• 라이언의 화살
  

  

  • 5발의 화살로 어피치의 점수를 빼앗는 첫 번재 방법은
    10점에 3발, 9점에 2발을 쏴서 10점과 9점을 빼앗는 방법이 있습니다.
    15(8+7) vs 19(10+9) 로 라이언이 승리합니다. 점수차는 4점이구요.

    
    

    근데 우리는 이기는 것이 목적이 아니라, 제일 점수차가 많이 나는 것을 찾는 게 목적입니다.
    즉, 점수를 빼앗으며 이기는 경우의 수를 모두 찾으면서 점수차를 비교하는 것이 핵심입니다.

    
    

    주의할 점은 점수를 빼앗을 만큼만 화살을 쏴야지, 낭비하면 안 된다는 점입니다. (어피치가 2발 쐈으면 3발, 어피치가 3발 쐈으면 4발 이런 식으로)
    예를 들어 우리는 9점을 더 많이 쏴서 이기고 싶을 수도 있지만, 9점을 포기하고 다른 점수를 비교할 수도 있죠.

• 라이언의 화살 - 9점을 포기한 경우
  

  

  
  이렇게 9점을 포기하고 8점을 비교한 점수차를 찾고
  또 8점을 포기하고 7점을 비교한 점수차를 찾고
  이렇게 모든 경우의 수를 비교하면서 점수차가 가장 큰 조합을 찾는 게 핵심입니다.

글로 풀어 쓰자면 10점을 무조건 가져간다는 경우의 수는

📌10점을 무조건 가져감

--------------------

🎈9점을 가져가고 나머지 조사

🎈9점을 포기하고 나머지 조사

--------------------

🎈8점을 가져가고 나머지 조사

🎈8점을 포기하고 나머지 조사

....

🎈1점을 가져가고 나머지 조사

🎈1점을 포기하고 나머지 조사

--------------------

기본적인 틀은 이렇습니다.

물론 10점도 마찬가지로 10점을 무조건 가져간다는 조건도 있지만, 10점을 포기하는 조건 하에 나머지를 조사하는 경우도 있어야 하구요.

• 점수차가 같은 경우에는 낮은 점수를 더 많이 맞춘 배열을 return 한다.
  기존에 가지고 있던 배열이랑 새로 구한 배열이 점수차가 같다? 그러면 두 배열을 뒤에서 부터 비교해서 값이 더 큰 것이 먼저 나오는 배열을 return 하면 됩니다.

---

문제 풀이

풀이 - 1

public class Solution {
    int len = 11, maxDiff = 0;
    int[] maxRyan = new int[len];

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

        return maxDiff > 0 ? maxRyan : new int[] { -1 };
    }

    public void getArcheryScore(int n, int[] info, int[] ryan, int score) {
        if(n == 0 || score == len) {            
            setMaxRyanAndDiff(info, ryan);
            return;
        }

        int arrow = 0;
        if(info[score] < n) arrow = info[score]+1;
        else if(score == len-1) arrow = n;

        int tmp = info[score];
        if(arrow > 0) {
            info[score] = 0;
            ryan[score] = arrow;
            getArcheryScore(n-arrow, info, ryan, score+1);
        } 
        info[score] = tmp;
        ryan[score] = 0;
        getArcheryScore(n, info, ryan, score+1);
    }

    public void setMaxRyanAndDiff(int[] info, int[] ryan) {
        int sum = 0;
        for(int i=0; i<len; i++) { if(info[i] > 0) sum -= 10-i; }
        for(int i=0; i<len; i++) { if(ryan[i] > 0) sum += 10-i; }

        if(this.maxDiff < sum) {
            for(int r=0; r<len; r++) { this.maxRyan[r] = ryan[r]; }
            this.maxDiff = sum;
        } else if(this.maxDiff == sum) {
            for(int i=len-1; i>=0; i--) {
                if(this.maxRyan[i] < ryan[i]) {
                    for(int r=0; r<len; r++) { this.maxRyan[r] = ryan[r]; }
                    break;
                } else if(this.maxRyan[i] > ryan[i]) {
                    break;
                }
            }
        }
    }
}

• 변수 초기화
  

  

  • len : 10~0 까지의 점수의 수
  • maxDiff : 가장 큰 점수차
  • maxRyan : 가장 큰 점수차의 라이언의 화살 배열

• 라이언 화살 쏘기 시작
  

  

  
  라이언 배열 초기화, 라이언은 10~0점 모두 0개로 세팅하고 시작합니다.
  • public void getArcheryScore(int n, int[] info, int[] ryan, int score)
    • n : 쏠 수 있는 화살의 개수
    • info : 어피치 화살 배열
    • ryan : 라이언 화살 배열
    • score : 구할 점수의 순서, 인덱스 (10점이면 0, 9점이면 1 ... 0점이면 10)

• 라이언 화살 쏘는 로직
  

  

  
  현재 점수에서 어피치가 쏜 화살의 수와 내가 가지고 있는 화살의 수를 비교해서
  내가 화살을 쏠 수 있으면 해당 화살 수를 구하고, 화살 수가 부족하면 무시
  
  

  점수가 마지막 점수인 0점에 도달했는데도 화살이 남았으면 남은 화살 수 전부 0점에 맞혔다고 가정

  
  

  • 경우1) 해당 화살 수를 구했으면 어피치는 어차피 점수를 못 가져가니까 0으로 바꾸고
    라이언에 화살 수를 저장하고 다음 점수 계산합니다.
    

    

  • 경우2) 화살을 쏠 수 있고 못 쏘고를 떠나서, 해당 점수를 포기하는 경우도 있으므로 (위에서 표로 설명)
    해당 점수는 포기하고 다음 점수 계산합니다.
    

    

  • 이렇게 다음 점수를 구하다가 화살을 모두 소진했거나, 점수가 0점에 도달하면 점수차 계산합니다.
    

    

• public void setMaxRyanAndDiff(int[] info, int[] ryan)

  • 어피치와 라이언의 점수차 계산
    

    

  • 최대 점수차보다 현재 점수차가 더 크면 교체
    

    

  • 라이언과 (현)라이언의 점수차가 같으면 더 낮은 점수를 많이 쏜 라이언을 찾아 교체할지 말지 결정
    

    

테스트 케이스 처리속도

테스트 1 〉	통과 (0.08ms, 75.3MB)
테스트 2 〉	통과 (0.61ms, 77.8MB)
테스트 3 〉	통과 (0.65ms, 75.9MB)
테스트 4 〉	통과 (0.26ms, 78.2MB)
테스트 5 〉	통과 (0.66ms, 76.7MB)
테스트 6 〉	통과 (0.76ms, 77.7MB)
테스트 7 〉	통과 (0.24ms, 72.7MB)
테스트 8 〉	통과 (0.14ms, 82.1MB)
테스트 9 〉	통과 (0.32ms, 76MB)
테스트 10 〉	통과 (0.09ms, 76.5MB)
테스트 11 〉	통과 (0.18ms, 83MB)
테스트 12 〉	통과 (0.17ms, 76.9MB)
테스트 13 〉	통과 (0.48ms, 76.8MB)
테스트 14 〉	통과 (0.55ms, 76MB)
테스트 15 〉	통과 (0.52ms, 79.2MB)
테스트 16 〉	통과 (0.34ms, 73.8MB)
테스트 17 〉	통과 (0.28ms, 82.5MB)
테스트 18 〉	통과 (0.05ms, 78.8MB)
테스트 19 〉	통과 (0.03ms, 74.6MB)
테스트 20 〉	통과 (0.50ms, 79.5MB)
테스트 21 〉	통과 (0.56ms, 72.8MB)
테스트 22 〉	통과 (0.61ms, 76.4MB)
테스트 23 〉	통과 (0.09ms, 71.8MB)
테스트 24 〉	통과 (0.57ms, 74.9MB)
테스트 25 〉	통과 (0.61ms, 72.4MB)