코테 준비 1일차

👑문제: [프로그래머스 Level2] https://school.programmers.co.kr/learn/courses/30/lessons/92342

문제 시 고려해야 할 점

1. 최대 점수가 아닌 최대 점수 차이를 구하는 것이다.
2. 모든 점수가 비기는 경우가 최소이므로 최소값은 0으로 설정해야 한다.
3. 동점인 경우 더 낮은 점수를 많이 맞춘 것이 답이다.

풀이 과정

class Solution {
    static int max = 0;
    static int answer[] = new int[11];
    static public int[] calTot(int []visited,int []info) {
        int lion = 0, apeach = 0;

        for(int i = 0; i< visited.length; i++) {
            if(visited[i] > 0) lion += (10 - i);
            else if(info[i] > 0) apeach += (10 - i);
        }
        return new int[]{lion, apeach};
    }

    static public void backtracking(int n, int index, int[] visited, int[] info) {
        if(n == 0 || index >= 10) {
            visited[10] = n;
            int[] tmp = calTot(visited,info);
            if(max <= tmp[0]-tmp[1] && tmp[0]-tmp[1] > 0) {
                int flag = 0;
                for (int i = visited.length-1; i >= 0; i--) {
                    if(visited[i] == 0 && answer[i]== 0)continue;
                    if(visited[i] < answer[i]){
                        flag = 1;
                        break;
                    }else if(visited[i] >= answer[i]) {
                        flag = 0;
                        break;
                    }
                }
                if(flag == 0 || max < tmp[0]-tmp[1]) {
                    for (int i = 0; i < visited.length; i++) {
                        answer[i] = visited[i];
                    }
                }
            }
            max = Math.max(max, tmp[0]-tmp[1]);
            return;
        }

        for(int i = index; i < info.length; i++) {
            //넘거나
            if(info[i]+1 <= n) {
                visited[i] = info[i]+1;
                backtracking(n-info[i]-1,i+1,visited,info);
            }
            //0점하거나
            visited[i] = 0;
            backtracking(n,i+1,visited,info);
        }
    }

    static public int[] solution(int n, int[] info) {
        int[] visited = new int[11];
        backtracking(n,0,visited,info);
        if(max == 0) return new int[]{-1};
        return answer;
    }
}

느낀점

문제 조건을 미리 주석으로 써놓은 뒤 설계를 마치고 들어가는 것이 좋겠다.
백트래킹인건 알았지만 세부적인 요소들에서 너무 시간을 많이썼다.