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

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라. 

    

- 우리가 풀어야 할 문제는 무엇인가?

-> 어피치가 n발을 다 쏜 후에, 라이언이 화살 n발을 쏜다

-> 가장 작은 원의 과녁 점수는 10점, 가장 큰 원의 바깥쪽은 과녁 점수가 0점

 

-k점을 어피치가 a발을 맞혔고, 라이언이 b발을 맞혔을 경우, 더 많은 화살을 k점에 맞힌 선수가 k점을 가져감

-> 단, a=b일 경우는 어피치가 k점을 가져감

-> 둘 다 a=b=0인경우는 누구도 k점을 가져가지 않음

-> 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산함

-> 최종 점수가 더 높은 선수를 우승자로 결정함

 

- 현재 상황은 어피치가 화살 n발을 다 쏜 후이고, 라이언이 화살을 쏠 차례임

-> 라이언이 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떻게 쏠 것인가?

-> 라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11

-> 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return함

 

- 이 의미가 무엇인가?

-> 이것의 의미가 무엇인가?

-> 이해했다

-> 낮은 점수를 기준으로 봐야 함

-> 라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1임

-> 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우,

 

- 어떻게 구하는가?

-> 즉, 어떻게 비교하는가?

-> 11개가 있다

-> 각각에 대해서 어떻게 비교하는가?

-> 총 몇 번을 쏘는가?

-> 5번을 쏜다

-> 이것을 어떻게 나타내는가?

-> 시간 복잡도가 어떻게 되는가?

-> 11개가 있다

 

-> n은 총 몇 까지 가능한가?

-> n이 10이다

-> 그렇다면 총 몇 가지 케이스가 존재하는가?

-> 11의 10승

-> 11의 10승이 몇인가?

-> 이걸 다 검사해야 하는가?

-> 250억이다

-> 당연히 이렇게 하면 안된다

-> 어떻게 해야 하는가?

-> 다 갈 필요가 없다

-> 무조건 어피치 보다 하나라도 많은 곳은 갈 필요가 없다

-> 따라서 그건 제외해준다

-> 둘 다 0 인 경우는 카운트 하지 않는다

-> 

- 또 문제가 있는가?

-> 예상하지 못한 문제가 있는가?

-> 코드를 어떻게 짤 수 있는가?

-> 

- 이 케이스는 어떻게 하는가?

-> 예를 들어 info 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 

-> 이것을 어떻게 하는가?

-> 하나라도 더 크면 걔는 더 이상 갈ㄹ 필요가 없다

-> 즉, 제외되어야 한다

-> 이것으로 다 해결이 된다

-> 그렇다면 무엇을 해야 하는가?

-> 여기까지 왔다

-> 이제 무엇을 해야 하는가?

-> 계산을 해야 한다

-> 무엇을 계산하는가?

-> 어떻게 계산을 하는가?

-

- 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법

이 여러가지 인 경우 어떻게 하는가?

-> 

 

- 문제가 무엇인가?

-> 어떻게 계산하는가?

-> if 0보다 작거나 같다면? 그냥 리턴함

-> 아니라면?

-> maxGap을 놓는다

-> 그리고 여기에 업데이트되는 경우 ArrayList<Integer>에 저장해놓는다

-> 그리고 만약에 같은 경우는 비교를 해서 더 작은 것을 넣는다

-> 이것을 어떻게 하는가?

-> 문제가 무엇인가?

-> 이것을 어떻게 접근하는가?

-> 접근한다는 것이 무엇인가?

-> 왜 이런 결과가 나오는가?

-> 시간이 많이 걸린다

-> 즉, 걸러내야 한다

-> 어떻게 걸러내는가?

-> 왜 이런 결과가 나오는가?

-> 

 

- 여기서 어떻게 걸러내는가?

-> 어디서 짤라내는가?

-> 짤라낸다는 것이 무엇인가?

-> 뒤에서 부터 하면 어떠한가?

-> 그러한 경우 어떻게 해야 하는가?

-> 어떻게 탐색 횟수를 줄이는가?

-> 탐색 횟수를 줄인다는 것이 무엇인가?

-> 다 돌 필요가 없다

-> 그것을 어떻게 없애는가?

-> 없앤다는 것이 무엇인가?

-> 그것을 어떻게 판단하는가?

-> 

10 9 8 7 6 5 4 3 2 1 0

 

10 9 8 6 5 4 

 

- 문제가 무엇인가?

-> 어떻게 해결할 것인가?

-> 해결한다는 것이 무엇인가?

-> 

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

[참고 코드]

import java.util.*; 

class Solution {
    
  
    public static int maxGap;
    public static int[] res = {-1};
    public static int[] lion;
    public static int N; 
    
    public int compare(int[] info, int[] lion){
        
        int apeachPoint = 0;
        int ryanPoint = 0;
        
        for(int i=0; i<11; i++){
            
            if(info[i] == 0 && lion[i] == 0){
                continue;
            }else if(info[i] >= lion[i]){
                apeachPoint += (10-i);
            }else{
                ryanPoint += (10-i);
            }
            
        }
        
        return ryanPoint-apeachPoint;
    }
    
    
    
    
    public void DFS(int cnt, int[] info, int[] lion){
        
        
        
        if(cnt == N){
        
            
            int gap = compare(info, lion);
            
            if(gap > 0){
                
                
                if(maxGap <= gap){
                    maxGap = gap;
                    res = lion.clone();
                }
                
            }
            
            return; 
            
            
        }    
        
        
        
        
        for(int i=0; i<11 && info[i] >= lion[i]; i++){
                lion[i] += 1;
                DFS(cnt+1, info, lion);
                lion[i] -= 1;
        }
        
        
    }
    
    
    
    
    
    public int[] solution(int n, int[] info) {
        maxGap = Integer.MIN_VALUE;
        lion = new int[11];
        N = n; 
        
        DFS(0, info, lion);
        
        
        return res;
    }
}

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?

-> maxGap보다 gap이 크거나 같을 때, 무조건 clone을 하면 된다

-> 왜냐하면 어차피 더 오른쪽에 있는 것이기 때문이다

-> 따라서 그냥 clone만으로 가능하다

 

- 왜 info[i] >= lion[i]를 저 위치에 넣어야 하는가?

-> 어차피 저 이하는 갈 필요가 없다

-> 따라서 for문을 굳이 돌면서 순회하는 것이 아니라

    앞에서 바로 끊어줌으로써 가지 않도록 하는 것이다.