[카카오] 양궁대회 (java)

문제링크

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

코딩테스트 연습 - 양궁대회

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트포스

(Test-Case 8번과 18번이 해결이 되지 않은 풀이입니다..)

양궁 문제를 브루트 포스로 해결하려고 시도하였다. 어피치와 라이언이 양궁을 진행하는데, 어피치가 각 점수에 맞춘 화살의 개수보다 1개만 많으면 해당 점수를 라이언이 가져간다. 라이언이 점수차를 가장 크게해서 이기는 방법을 찾는 문제이다.

 

먼저 어피치가 쏜 화살의 정보를 확인하고 재귀를 통해 어느 점수를 라이언이 취득할 것인지 판단하였다. 

for (int i = start; i < info.length; i++) {
    if (n > info[i]) {
        shots[i] = info[i] + 1;
        shot(n - (info[i] + 1), i + 1, info, shots);
        shots[i] = 0;
    }
}

10점부터 차례대로 재귀를 돌려가며 화살을 쏘게 하였고, 모든 화살을 소모하게 된 경우에는 점수를 판단하고 차이를 계산하여 최대로 점수가 차이나는 값으로 쏘는 경우를 변경하였다. 그리고 만약 최대로 차이가나는 점수가 동일하다면 가작 적은 점수를 많이 쏜 것을 출력해주어야 하므로 같은 점수대가 나온 경우도 처리하여주었다.

if (n == 0) {
    int calPoint = calPoint(info, shots);
    if (calPoint > maxPoint) {
        maxPoint = calPoint;
        for (int i = 0; i < result.length; i++) {
            result[i] = shots[i];
        }
    }
    else if(calPoint == maxPoint){
        boolean change = false;
        for(int i = result.length-1; i >=0; i--) {
            if (result[i] < shots[i]) {
                change = true;
                break;
            }
        }
        if(change){
            for (int i = 0; i < result.length; i++) {
                result[i] = shots[i];
            }
        }
    }

 

이렇게 브루트포스로 모든 경우를 탐색하여 문제를 해결하였지만, 2가지 테스트케이스를 통과하지 못하였다. 

문제를 해결하고 글에 추가로 설명을 붙이도록 하겠다.

구현코드

package pgm_92342;

public class Solution {
    int[] result = new int[11];
    int maxPoint = Integer.MIN_VALUE;

    public int[] solution(int n, int[] info) {
        int[] answer;
        shot(n, 0, info, new int[11]);
        if (maxPoint <= 0)
            answer = new int[]{-1};
        else
            answer = result;
        return answer;
    }

    public void shot(int n, int start, int[] info, int[] shots) {
        if (n == 0) {
            int calPoint = calPoint(info, shots);
            if (calPoint > maxPoint) {
                maxPoint = calPoint;
                for (int i = 0; i < result.length; i++) {
                    result[i] = shots[i];
                }
            }
            else if(calPoint == maxPoint){
                boolean change = false;
                for(int i = result.length-1; i >=0; i--) {
                    if (result[i] < shots[i]) {
                        change = true;
                        break;
                    }
                }
                if(change){
                    for (int i = 0; i < result.length; i++) {
                        result[i] = shots[i];
                    }
                }
            }
            return;
        }
        for (int i = start; i < info.length; i++) {
            if (n > info[i]) {
                shots[i] = info[i] + 1;
                shot(n - (info[i] + 1), i + 1, info, shots);
                shots[i] = 0;
            }
        }
        shots[10] += n;
        shot(0, 0, info, shots);
        shots[10] -= n;
    }

    public int calPoint(int[] info, int[] shots) {
        int point = 0;
        for (int i = 0; i < info.length; i++) {
            if (info[i] == 0 && shots[i] == 0)
                continue;
            if (info[i] < shots[i])
                point += (10 - i);
            else
                point -= (10 - i);
        }
        return point;
    }
}

 

시간복잡도

n개의 화살이 각각 어디로 쏴야하는지 계산해주면 굉장히 오래 걸리게 된다. 하지만 각 화살들이 어느 과녁으로 쐇는지는 중요하지 않다. 그리고 어피치가 맞춪 과녁의 화살의 수 +1 만큼으로만 쏴줘야한다.  따라서 어느 점수를 취득할 것인지를 골라주는 정도의 시간복잡도가 소요된다. 

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)
추가로.. 저의 코드에서 오류가 있는 점을 발견하셨다면, 댓글로 알려주시면 감사하겠습니다.