양궁 대회

2022 KAKAO BLIND RECRUITMENT

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

프로그래머스

실행 결과 : 실패

---

라이언이 가장 큰 점수 차이로 우승할 때 과녁에 맞춘 갯수를 리턴하는 문제이다.

쏠 수 있는 화살의 갯수가 5개일 때, 라이언이 화살을 쏘는 경우는 다음과 같이 표현할 수 있다.

[9, 9, 8, 8, 6] ➡ 9점 2개, 8점 2개, 6점 1개

그런데 [9, 9, 8, 8, 6] 이나 [9, 8, 8, 9, 6] 이나 9점 2개, 8점 2개, 6점 1개를 맞춘 것은 같다.

즉, 중복조합을 이용해서 라이언이 화살을 쏘는 경우의 수를 구할 수 있다.

중복조합의 공식

1. 중복 조합을 이용해 라이언이 화살을 쏘는 경우를 구한다.

  - [9, 9, 8, 8, 6] ➡ 9점 2개, 8점 2개, 6점 1개

2. 화살을 쏘는 경우를 구했다면 해당 경우의 수를 활용해 라이언이 과녁에 몇 개를 맞췄는지 구한다.

  - [9, 9, 8, 8, 6] ➡ 9점 2개, 8점 2개, 6점 1개 ➡ [0, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0]

3. 어피치와 라이언의 과녁 정보를 비교해서 어피치의 점수와 라이언의 점수를 계산한다.

  - 라이언이 어피치보다 과녁에 맞춘 갯수가 많을 때 라이언이 점수를 가져간다.

  - 단, 둘다 맞추지 않았다면 둘다 점수를 가져가지 않는다.

4. 라이언의 점수와 어피치 점수 차를 구한다. 이 값이 0과 같거나 작으면 재귀를 종료하고 또한 이 값이 최대차이점수보다 작으면 마찬가지로 재귀를 종료한다.

5. 최대차이점수보다 크면 최대차이점수를 업데이트하고 ret에 라이언의 과녁정보를 넣는다.

6. 최대차이점수와 같다면 가장 작은 점수부터 비교해서 작은 점수를 많이 맞춘 정보를 ret에 넣는다.

 

구현

구현에 실패했던 이유는 중복조합 함수를 잘못 구현했다.

combi 함수를 재귀호출할 때 인자로 start가 아닌 i를 넣어야하는데 start를 넣어서 불필요한 중복을 계산했기 때문에 시간초과가 나왔다.

function solution(n, info) {
    let ret;
    let max = Number.MIN_SAFE_INTEGER;
    const points = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
    
    function combi(start, b){
        if(b.length === n){
            let lionPoint = 0;
            let apechPoint = 0;
            const lion = Array.from({length: 11}).fill(0);
            b.forEach((num)=> lion[10 - num]++);
            info.forEach((num, idx) => {
                if(num !== 0 || lion[idx] !== 0) {
                    if(num < lion[idx]) lionPoint += 10 - idx;
                    else apechPoint += 10 - idx;
                }
            });
            const d = lionPoint - apechPoint;
            if(d <= 0 || max > d) return;
        
            if(max < d) {
                max = d;
                ret = lion;
            }
            else if(max === d) {
                for(let i = 10; i >= 0; i--){
                    if(ret[i] > lion[i]) break;
                    else if(ret[i] < lion[i]){
                        ret = lion;
                        break;
                    }
                }
            }
            return;
        }
        else {
            for(let i = start; i <= 10; i++) {
                b.push(points[i]);
                combi(i, b); // i를 넣어주어야한다.
                b.pop();
            }
        }
    }
    
    combi(0, []);
    if(!ret) return [-1];
    return ret;
}