[프로그래머스/자바] 양궁대회 풀이 - 2022 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2022 KAKAO BLIND RECRUITMENT Level 2 문제다.

 

 

info가 11, n의 최대가 10이므로 가장 먼저 백트래킹 DFS를 떠올렸다.

DFS가 진행될수록 result에 화살을 쏜 개수를 저장한다.

라이언이 무조건 이겨야하는 경우만 고려하면 되므로, 어피치가 쏜 화살보다 한개 더 많은 화살을 쏜다고 가정했다.

라이언이 화살을 쏠 때마다 cnt를 감소시켜서, 남은 화살의 개수를 계산한다. (cnt는 가장 처음 n으로 시작)

라이언이 쏴야할 화살만큼 남은 화살이 존재하지 않는다면, 남은 화살 모두를 쏜다.

 

그리고 라이언이 어피치를 이겼을 경우 그 점수의 차이를 max에 갱신해준다.

ArrayList에 라이언이 어피치를 이겼을 경우의 result[](화살 개수를 저장한 배열)를 저장하는데,

max가 갱신될 때마다 ArrayList를 비워줌으로써

ArrayList에는 차이가 최대가 되는 화살의 경우만 저장되게 한다.

 

DFS를 다 돈 후

ArrayList에 아무것도 들어있지 않다면 라이언이 이길 수 없는 경우이므로 -1 반환,

ArrayList에 하나만 들어있다면 라이언이 이길 수 있는 경우가 하나이므로 그 값을 바로 꺼내서 반환,

ArrayList에 두개 이상이 들어있다면 ArrayList의 모든 값을 비교해 가장 낮은 점수를 많이 맞힌 경우를 찾아서 반환한다.

 

    // 가장 낮은 점수를 더 많이 맞힌 경우를 반환
    static int[] compareScore(int[] s1, int[] s2) {
    	int[] arr = s1;
    	
    	for(int i=10;i>=0;i--)
    		if(s1[i] > s2[i]) 
    			break;
    		else if(s1[i] < s2[i]) {
    			arr = s2;
    			break;
    		}
    	
    	return arr;
    }

낮은 점수를 많이 맞힌 경우를 찾기 위해 위와 같은 코드를 작성했다.

 

        if(list.size() == 0)
            return new int[] {-1};
        else if(list.size() == 1) {
            answer = list.get(0);
        }
        else {
        	answer = list.get(0);
        	for(int i=1;i<list.size();i++) 
        		answer = compareScore(answer, list.get(i));
        }
        return answer;

그리고 solution 메소드에서

ArrayList에 두개 이상 들은 경우에 compareScore()를 사용해 list끼리 비교하고,

answer에 가장 낮은 문제를 많이 맞힌 경우를 갱신하도록 구현했다.

 

		list.sort((o1, o2) -> {
			for(int i=10;i>=0;i--)
				if(o1[i] != o2[i])
					return o2[i] - o1[i];
			return 0;
		});

배열을 하나하나 비교하지 않고 sort해도 된다.

람다식으로 Comparator를 여러번 구현해봤지만,

정렬할 기준이 여러 인덱스인 경우(최악의 경우 인덱스 10부터 0까지 모두 탐색해야 하므로)

어떻게 해야할지 몰라 구글링해서 찾았다.

 

Comparator를 구현할때 람다식이 아닌 위와 같이 for문을 사용해도 된다는 걸 또 배웠다!

이렇게 구현하는 게 코드도 짧고 간단하지만,

성능은 직접 compareScore 메소드를 구현하는게 더 좋았다. (2배 정도 차이남)

 

 

문제 자체가 깔끔하지 못해서, 알고리즘에 대한 고민보다 문제를 이해하는데 시간을 더 많이 쓴 거 같은 문제다 ㅋㅋㅋ

 

import java.util.*;

class Solution {
    static ArrayList<int[]> list = new ArrayList<>();
    static int[] result = new int[11];
    static boolean[] visit = new boolean[11];
    static int max = -1;
    
    public int[] solution(int n, int[] info) {
        DFS(0, n, info);
        
        int answer[] = new int[10];
        
        if(list.size() == 0)
            return new int[] {-1};
        else if(list.size() == 1) {
            answer = list.get(0);
        }
        else {
        	answer = list.get(0);
        	for(int i=1;i<list.size();i++) 
        		answer = compareScore(answer, list.get(i));
        }
        return answer;
    }
    
    static void DFS(int start, int cnt, int[] info) {
        if(cnt == 0) {
            int diff = getScoreDiff(info, result);
            if(diff > 0) {
                if(max == diff)
                    list.add(result.clone());
                else if(max < diff) {
                	max = diff;
                    list.clear();
                    list.add(result.clone());
                }
            }
            return;
        }
        
        for(int i=start;i<11;i++) {
            if(!visit[i]) {
                visit[i] = true;
                int arrow = info[i] + 1; // 어피치보다 하나 더 쏘기
                if(arrow > cnt) 
                    arrow = cnt; // 쏠 화살이 부족할 경우 남은 화살 모두 쏘기
                result[i] = arrow;
                DFS(i, cnt - arrow, info);
                visit[i] = false;
                result[i] = 0;
            }
        }
    }
    
    // 라이언이 이길 경우 점수의 차이를, 어피치가 이길 경우 -1를 반환
    static int getScoreDiff(int[] info, int[] result) {
        int score[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        int apeach = 0;
        int ryan = 0;
        
        for(int i=0;i<11;i++) {
            if(info[i] == 0 && result[i] == 0)
                continue;
            else if(info[i] >= result[i])
                apeach += score[i];
            else 
                ryan += score[i];
        }
        
        if(apeach >= ryan)
            return -1;
        
        return ryan - apeach;
    }
    
    // 가장 낮은 점수를 더 많이 맞힌 경우를 반환
    static int[] compareScore(int[] s1, int[] s2) {
    	int[] arr = s1;
    	
    	for(int i=10;i>=0;i--)
    		if(s1[i] > s2[i]) 
    			break;
    		else if(s1[i] < s2[i]) {
    			arr = s2;
    			break;
    		}
    	
    	return arr;
    }
}