프로그래머스 - 양궁대회

프로그래머스 2022 KAKAO BLIND RECRUITMENT lv2 양궁대회 문제를 풀어보았다.

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=java 

프로그래머스

1. 양회

풀이 시간: 40분

생각보다 쉽게 풀어서 기분이 좋았다!

---

 

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=java

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=java

이전 우승자 라이언과 결승 진출자 어피치가 양궁대회를 치르는데, 0~10점까지 과녁에 n개의 화살을 쏴 점수를 비교하여 우승자를 겨룬다.

주어진 조건은 다음과 같이 정리하였다.

1. k점에 해당하는 과녁을 둘 다 0번 맞히면 가져가는 점수는 없다. (최종 점수 계산 시 사용)
2. 동일한 개수의 화살을 k점 과녁에 맞췄다면 어피치가 점수를 가져감
3. 라이언이 가장 큰 점수차이로 우승하도록 하는 배열을 반환하라, 이기지 못하면 {-1} 반환

제한 사항

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=java

제한사항을 보면 다음과 같다.

1. 라이언이 큰 점수차이로 우승할 때의 맞춘 화살 배열을 반환
2. 점수차이가 같게 이기는 경우가 더 존재하면 라이언이 낮은 점수를 많이 맞춘 배열 반환

---

문제 풀이

1. 0~10점의 과녁을 맞춘경우와 못 맞춘 경우를 완전탐색하면 된다고 생각하였고, 그 과정에서 백트래킹을 하면 된다고 판단하고 dfs + 백트래킹 부분을 먼저 코딩
2. 점수를 비교하여 승자를 정해야하는데, 10-i 점이라는 제한사항을 이용해 계산하였고, lion이 맞춘 화살 개수가 info보다 크면 더하기를, 작으면 마이너스를 하였다.
   1. 만약 lion[i] > info[i]가 아닌 경우에는 info[i]가 0인지 체크 -> 0이면 pass
3. 계산한 점수차이와 현재 큰 점수 차이가 동일하다면 lion 배열의 역순으로 탐색하여 낮은 점수가 더 큰 경우의 배열을 results로 clone 한다.

초기 코드

import java.util.*;
class Solution {
    public static int diff = 0;
    public static int[] results;
    public int[] solution(int n, int[] info) {
        results = new int[info.length];
        int[] lion = new int[info.length];
        dfs(info, lion, n, 0);
        return diff == 0 ? new int[]{-1} : results;
    }
    public void dfs(int[] info, int[] lion, int n, int cnt){
        if(cnt == n){
            int dif = 0;
            for(int i=0; i<info.length; i++){
                if(lion[i] > info[i]){
                    dif += 10 - i;
                }
                else if(info[i] != 0) dif -= 10 - i;
            }
            if(dif > diff) {
                diff = dif;
                results = lion.clone();
            }
            else if(dif == diff){
                for(int i=info.length-1; i>=0; i--){
                    if(lion[i] > results[i]){
                        results = lion.clone();
                        return;
                    }
                }
            }
            return;
        }
        for(int i=0; i<info.length; i++){
            lion[i] += 1;   // 맞춤
            dfs(info, lion, n, cnt+1);
            lion[i] -= 1;   
        }
    }
}

처음 짠 코드를 제출하니 시간이 10초 초과되었다며 더 빠른 방법을 알아보라고 나타났다.

 

시간 초과..

 

시간  초과가 발생하니 제외할 수 있는 상황을 제외해야 한다고 판단하였고

가장 큰 점수차이를 발생시키기 위해, lion의 10 - i점을 맞춘 화살이 이미 info보다 커졌다면 더 가지를 쳐나갈 필요가 없다.

 

start

[0,0,0,0,0,0,0,0,0,0,0]

 

첫 dfs 루프

[1,0,0,0,0,0,0,0,0,0,0]

[0,1,0,0,0,0,0,0,0,0,0]

[0,0,1,0,0,0,0,0,0,0,0]

[0,0,0,1,0,0,0,0,0,0,0]

[0,0,0,0,1,0,0,0,0,0,0]

...

만약 10점이 주어진 info에서 0이었다면

두 번째 dfs에서 맨 처음 lion에 대한 dfs만 보면 [1,0,0,0,0,0,0,0,0,0,0]

[2,0,0,0,0,0,0,0,0,0,0]

[1,1,0,0,0,0,0,0,0,0,0]

[1,0,1,0,0,0,0,0,0,0,0]

[1,0,0,1,0,0,0,0,0,0,0]

[1,0,0,0,1,0,0,0,0,0,0]

...

10점이 2발 맞는 경우로 가지를 쳐 나갈 필요는 없다. 

-> 조건을 하나만 추가하면 된다.!

for(int i=0; i<info.length; i++){
	if(lion[i] > info[i]) continue;
    lion[i] += 1;   // 맞춤
    dfs(info, lion, n, cnt+1);
    lion[i] -= 1;   
}

처음엔 continue로 [1,1,0,0,0,0,0,0,0,0,0]에서 뻗어나가는 가지는 필요하다고 생각했다. (여전히 시간초과)

하지만... 맨 처음 dfs가지의 두 번째를 보면 [0,1,0,0,0,0,0,0,0,0,0]에서 [1,1,0,0,0,0,0,0,0,0,0]로 뻗어나가기 때문에

더 진행할 필요가 없다는 것이다..

continue를 break로 변경하면 탐색 횟수가 획기적으로 줄어들고 통과한다..!

 

최종 코드

import java.util.*;
class Solution {
    public static int diff = 0;
    public static int[] results;
    public int[] solution(int n, int[] info) {
        results = new int[info.length];
        int[] lion = new int[info.length];
        dfs(info, lion, n, 0);
        return diff == 0 ? new int[]{-1} : results;
    }
    public void dfs(int[] info, int[] lion, int n, int cnt){
        if(cnt == n){
            int dif = 0;
            for(int i=0; i<info.length; i++){
                if(lion[i] > info[i]){
                    dif += 10 - i;
                }
                else if(info[i] != 0) dif -= 10 - i;
            }
            if(dif > diff) {
                diff = dif;
                results = lion.clone();
            }
            else if(dif == diff){
                for(int i=info.length-1; i>=0; i--){
                    if(lion[i] > results[i]){
                        results = lion.clone();
                        return;
                    }
                }
            }
            return;
        }
        for(int i=0; i<info.length; i++){
            if(lion[i] > info[i]) break;
            lion[i] += 1;   // 맞춤
            dfs(info, lion, n, cnt+1);
            lion[i] -= 1;   
        }
    }
}

---

마지막 조건은 찾기 어려웠다.. 하지만 좋은 아이디어이기에 잘 활용할 수 있도록 정리하였다!