프로그래머스 - 양궁 콘테스트

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

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

프로그래머스

코드 중심 개발자 채용. 스택 기반 포지션 매칭 프로그래머스 개발자를 위한 커스텀 프로파일을 등록하고 나와 기술의 궁합이 잘 맞는 기업을 매칭합니다.

인기글

programmers.co.kr

캠퍼스

수영장 시간: 40분

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

문제 설명

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

이전 승자 라이언그리고 결승 진출자 아피치양궁 대회를 개최하지만 0~10포인트까지 n개 화살을 쏴 스코어를 비교해 우승자를 겨룬다.

주어진 조건은 다음과 같이 요약되었다.

k점에 해당하는 목표를 양쪽 모두 0회 맞으면 취하는 점수는 없다.

(최종 점수 계산에 사용)
같은 개수의 화살을 k점에 맞추면, 아피치가 스코어를 취한다
라이언이 최대 점수 차이로 이길 수 있는 배열을 반환하고, 이길 수 없는 경우 {-1}을 반환합니다.

제한사항

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

라이언이 큰 점수 차이로 우승했을 때 맞춘 화살의 배열을 반환
스코어 차이가 동일하게 이기는 경우가 더 존재한다면, 라이언은 낮은 점수를 많이 정렬한 배열 반환

문제 해결

0~10점의 목표를 맞춘 경우와 맞지 않은 경우를 완전 탐색하면 좋다고 생각하고, 그 과정에서 백트래킹을 하면 된다고 판단하고, dfs+백트래킹 부분을 먼저 코딩
점수를 비교해 승자를 결정해야 하지만, 10-i점이라는 제한사항을 이용해 계산하고, lion이 맞춘 화살 개수가 info보다 크면 플러스를, 작다고 마이너스를 했다.
1. lion(i) > info(i)가 아닌 경우 info(i)가 0인지 확인 – > 0이면 pass
계산한 스코어차이와 현재의 큰 스코어차이가 같으면, 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보다 커지고 있으면 더 가지를 칠 필요는 없다.

시작

(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점이 주어진 정보로 0이면

두 번째 DFS에서 첫 번째 라이온의 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;   
        }
    }
}

마지막 조건은 찾기가 어려웠다 .. 그러나 좋은 아이디어이기 때문에 잘 활용할 수 있도록 정리했다!

프로그래머스 – 양궁 콘테스트

인기글