[프로그래머스] [Level2] 양궁대회 JAVA

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

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

[문제]

[풀이]

완전탐색 + 그리디 문제이다.

1. 맞출 수 있는 모든 과녁을 중복을 포함하게 탐색할 것
2. 누군가 득점을하면 나머지 하나는 득점을 하지 못함
3. 가장 낮은 점수를 많이 맞춘 순 으로 리턴할 것

이 세가지만 만족하면서 탐색하여 depth 가 주어진 n 만큼 진행하고 정산한 결과를 리턴해주면 된다.

import java.util.*;
import java.io.*;
import java.util.stream.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Solution solution = new Solution();
        int[] result = solution.solution(5, new int[]{2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0});
        System.out.println(Arrays.toString(result));
    }
}
class Solution {
    int[] appeach,ryan;
    int n,max;
    Queue<int[]> answer = new PriorityQueue<>(((o1, o2) -> { // 가장 낮은점수를 많이 맞춘 경우가 우선
        for (int i = 10; i >= 0; i--)
            if (o1[i] != o2[i]) return o2[i] - o1[i];
        return 0;
    }));

    public int[] solution(int n, int[] info) {


        init(n, info);
        dfs(0,0);
        if(answer.isEmpty())
            return new int[]{-1};
        return answer.poll();

    }

    private void init(int n, int[] info) {
        this.appeach = info.clone();
        this.ryan = new int[11];
        this.n = n;
        this.max=-1;
    }

    public void dfs(int cur,int depth){

        if(depth == n){
            // 정산

            int appeachSum=0,ryanSum=0;
            for(int i=0;i<=10;i++){
                if(appeach[i] < ryan[i]) ryanSum+=10-i;
                else if(appeach[i]!=0) appeachSum+=10-i;
            }

            // 라이언이 못 이기는 경우 or 현재까지 라이언의 점수합보다 낮은 경우
            if(ryanSum<=appeachSum || ryanSum-appeachSum < max)
                return;

            if (ryanSum - appeachSum > max) {
                max = ryanSum - appeachSum;
                answer.clear(); // max가 갱신되면 큐 클리어
            }
            answer.add(ryan.clone());
            return;
        }

        for(int next=cur;next<=10;next++){
            ryan[next]++;
            dfs(next,depth+1);
            ryan[next]--;
        }
    }
}​