Level 2️⃣ - 양궁대회

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

프로그래머스

🚀문제 접근

핵심 요구사항

라이언이 가장 큰 점수차로 이기는 경우를 구해야한다.

 

설계

1. 라이언이 과녁을 맞추는 경우의 수를 구한다.

  - 경우의 수를 중복순열을 이용해서 구한다.

 

2. 라이언이 과녁을 맞춘 경우의 수를 토대로 라이언의 Info를 만든다. 그리고 어피치와 라이언의 Info를 비교해서 각각의 점수를 계산한다. 만약 라이언이 이기는 경우라면 라이언의 점수와 라이언의 Info를 저장한다.

 

3. 라이언이 이기는 경우에 저장된 라이언의 점수와 일치하는 경우가 있다. 예를 들어 25점차이로 이기는 경우가 두 개 이상 존재할 수도 있다. 이럴 때는 가장 낮은 점수를 많이 맞춘 경우의 Info를 정답으로 해야한다. 만약 라이언의 점수가 어피치의 점수와 동일하거나 낮은 경우에는 [-1]을 리턴하도록 한다.

 

설계 수정

이 문제에서 가장 시간을 오래 잡아먹은 부분은 라이언이 과녁을 맞추는 경우의 수를 구하는 부분과 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return하는 부분이었다.

 

처음에 중복순열을 이용해서 경우의 수를 구하려고 했으나 n이 최대 10이다. 이렇게 될 경우 중복 순열을 활용하면 과녁을 맞출 수 있는 경우의 수가 0점부터 10점까지 총 11가지이기 때문에 11^10 이 된다. 매우 큰 수 이기 때문에 시간초과가 날 수 있다.

따라서 설계를 수정하기로 했다. 예를 들어 10점부터 0번째 과녁 ~ 0점은 10번째 과녁이라고 생각하자.

[1, 1, 2, 2, 4] 이렇게 라이언이 과녁을 맞췄다. 이 경우는 라이언이 9점 2번, 8점 2번, 6점 1번을 맞춘 경우이다.

그런데 [2, 1, 2, 1, 4] 이렇게 맞춘 경우에도 라이언은 9점 2번, 8점 2번, 6점 1번을 맞춘 경우이다. 중복 순열로 구하는 것이 아니라 중복 조합을 활용하면 시간복잡도를 줄일 수 있을 것이라고 판단했다. 

// 조합
function combi(start, b){
    if(b.length === n){
        return;
    }
    else{
        for(let i = start+1; i<n; i++){
            b.push(i);
            combi(i, b);
            b.pop();
        }
    }
}

// 중복조합
function combi(start, b){
    if(b.length === n){
        return;
    }
    else{
        for(let i = start; i<n; i++){
            b.push(i);
            combi(i, b);
            b.pop();
        }
    }
}

 

재귀를 활용한 중복조합을 이용하면 같은 점수차이로 어피치를 이긴 경우에 뒤에 오는 값이 가장 낮은 점수를 더 많이 맞힌 경우라고 생각을 했다. 하지만 오해였다. 같은 점수차이로 이긴 경우라면 어떤 값이 더 낮은 점수를 많이 맞혔는지 확인하는 로직이 필요했다.

사실 이 부분이 가장 시간이 오래걸렸다. 반례를 전혀 생각하지 못했기 때문이다.

 

구현

function solution(n, info) {
    let ret;
    let max = Number.MIN_SAFE_INTEGER;
    function combi(start, b){ // 중복조합을 활용
        if(b.length === n){
            let apeachScore = 0;
            let lionScore = 0;
            const lionInfo = Array.from({length : 11}).fill(0);
            b.forEach((num)=>{
                lionInfo[num] += 1;
            });
            info.forEach((num, idx)=>{
                if(info[idx]!==0 || lionInfo[idx]!==0){
                  if(info[idx] < lionInfo[idx]) lionScore += 10 - idx;
                  else apeachScore += 10 - idx;
                }
            });
            let d = lionScore - apeachScore;
            if(d >= max){
                if(d <= 0) ret = [-1]; // 라이언의 점수가 어피치의 점수보다 낮거나 같은 경우
                else if(d === max){ // 가장 낮은 점수를 더 많이 맞힌 경우를 리턴해야한다.
                    for(let i = 10; i>=0; i--){
                        if(ret[i] < lionInfo[i]){
                            ret = lionInfo;
                            break;
                        }
                        else if(ret[i] > lionInfo[i]) break;
                    }
                }
                else if(d > max){ // 가장 큰 점수 차이로 우승하는 방법을 구해야한다.
                    ret = lionInfo;
                    max = d;
                }
            } 
            return;
        }
        else{
            for(let i = start; i <= 10; i++){
                b.push(i);
                combi(i, b);
                b.pop();
            }
        }
    }
    combi(0, []);
    
    return ret;
}