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

프로그래머스 - 양궁대회

링크 : 프로그래머스 - 양궁대회
레벨 : 2
출처 : 카카오 2022 블라인드 공채 기출문제

1) 문제 해석

• 최종 구현 요구 사항 : 라이언이 어피치를 이기는 케이스 중 가장 큰 점수차로 이기는 케이스를 배열에 담아 리턴하는 것

• 추가 조건
  1) 만약에 가장 큰 점수차로 이기는 케이스가 여러개면 그중에서는 작은 점수를 한개라도 더 맞춘 케이스를 선택해서 리턴
  2) 만약에 라이언이 어떤 방법으로도 어피치를 이길 수 없다면 [-1]을 리턴
  3) 어피치에게 어드밴티지를 주는 방향으로 진행을 하기 때문에 만약 같은 점수를 같은 개수만큼 맞췄다면 어피치가 승리하고, 최종적으로 점수가 같을 때도 어피치가 승리한다(* 둘다 한발도 못맞추면 점수로 치지 않는다)

• 문제 분석 :
  1) 어피치가 쏜 결과는 알려주기 때문에 그 결과를 바탕으로 라이언이 쏠 수 있는 화살의 개수 n으로 시뮬레이팅을 해보는 문제임.
  2) 그 시뮬레이팅 중에 라이언이 어피치를 이길 수 있는 케이스를 찾는 것을 1차적 목표로 하고, 2차적으로 가장 높은 점수차로 이긴 점수를 리턴하는게 목표이다.

2) 문제 설계

코드 작성 이전에 설계

• 라이언이 어피치를 이기는 케이스를 1차적으로 탐색하는게 목표이기에 완전탐색을 해본다. 이 때, 라이언이 질만한 케이스는 고려할 필요가 없으므로 라이언의 화살개수 n과 어피치의 결과를 가지고 라이언이 이길 수 있는 방향만 고려한다.
• 라이언이 이길 수 있는 방향이라 했을 때, 어피치보다 1발만더 맞추는 방향으로의 생각을 떠올릴 수 있다. 즉, 라이언이 어피치가 맞춘 화살의 개수 + 1을 맞춰서 해당 점수를 가져가느냐 or 아예 0발을 맞추고 해당 점수는 어피치에게 주느냐의 선택 두개로 나눠서 생각한다.
• 이렇게 두개의 선택지를 가지고 라이언이 특정 점수에서 이기고 다른 점수에서는 지는 방향으로 생각할 수 있는 모든 케이스를 완전 탐색한다.
• 이 때 완전탐색은 재귀함수 + DFS로 구현한다.
• 재귀 함수의 기저조건에서 이전 점수차를 비교하고, 만약에 지금 비교중인 점수차가 더 크면 교체해준다.
• 이 때, 점수차가 동일하다면 가장 작은 수부터 비교해서 작은 점수에 맞춘 화살의 개수가 더 많은 쪽에 가중치를 둔다.

코드 설계

• 재귀함수의 기저조건으로 idx === 10 || n === 0 을 써준다
• 그리고 그안에 이전 maxScore와 점수차가 동일한 경우와 아닌 경우를 분기처리해서 만약에 아니면 그대로 maxScore(점수차)가 더 큰 경우로 교체해주고, 동일하면 작은 점수를 많이 맞춘 쪽을 선택한다. 이 때의 로직은 for문으로 가장끝 값을 차례로 비교해가도록 하되 작은 수에 더 높은 화살의 개수를 맞춘 케이스가 나오자마자 바로 리턴한다. 즉, draw가 아닌 이상 이 for문은 바로 끝날수도 있다.
• 기저조건이 아닌 일반적인 실행문에는 라이언의 점수 시뮬레이팅 로직이 들어가야한다. 이 때의 로직은 앞에(10점부터)서부터 어피치를 이길지 말지로 분기처리를 해놓는다.
• 분기처리 로직 : n이 어피치가 특정 점수대에서 맞춘 화살의 개수보다 많다면 라이언이 이길수 있는 케이스이기에 어피치가 맞춘 개수 +1 만큼 n에서 차감하고 라이언이 맞춘 점수를 담는 배열에 담는다. 그리고 다음 재귀 로직으로 넘어가되 idx++을 해준다. 그럼 그 다음 재귀함수에서도 똑같은 시행을 하는데, 다시 분기처리로 돌아와서 만약 n이 어피치가 맞춘 화살의 개수보다 적게 남았다면(혹은 같다면) 라이언이 못이기는 상황이기에 n을 투자하지 않고 idx++만 해주고 넘어간다(다음 재귀함수로) 그렇게 쭉 기저조건에 닿을때까지 진행한다.
• 위의 분기처리 로직대로 진행하고 기저조건에 닿고, return을 하면 이전 시행으로 돌아온 다음에
  - 만약 이전 로직에서 라이언이 이길 수 있는 상황이었다면 다시 돌아와서(재귀함수로부터) idx--, scoreBoard에 추가했던 라이언이 맞춘 화살개수를 다시 되돌리는 작업 후에 다시 어피치가 이기는 케이스로 간다.

구두로 작성해서 복잡한데, 결론적으로 재귀함수 안에서는 라이언이 이기는 케이스로 DFS를 진행하는 것이라고 생각하면 된다. 가장 높은 점수(10, 9, 8점 등)에서 먼저 라이언이 이길 수 있다면 그 이길 수 있는 케이스를 중심으로 DFS를 진행하고, 그 케이스를 진행한 뒤에는 그 점수대에서 진다는 케이스로 다시 DFS를 진행하고 이런식이다.

3) 실제 코드 구현
: 위에서 구두로 설명한 부분을 실제로 코드로 옮겨보자.

• 재귀함수의 기저조건으로 idx === 10 || n === 0 을 써준다

const recursion = (idx) => {
	if(idx === 10 || n === 0 ) {
		// 기저조건
	}
}

• 그리고 그안에 이전 maxScore와 점수차가 동일한 경우와 아닌 경우를 분기처리해서 만약에 아니면 그대로 maxScore(점수차)가 더 큰 경우로 교체해주고, 동일하면 작은 점수를 많이 맞춘 쪽을 선택한다. 이 때의 로직은 for문으로 가장끝 값을 차례로 비교해가도록 하되 작은 수에 더 높은 화살의 개수를 맞춘 케이스가 나오자마자 바로 리턴한다. 즉, draw가 아닌 이상 이 for문은 바로 끝날수도 있다.
  기저조건이 아닌 일반적인 실행문에는 라이언의 점수 시뮬레이팅 로직이 들어가야한다. 이 때의 로직은 앞에(10점부터)서부터 어피치를 이길지 말지로 분기처리를 해놓는다.

const maxScore = [-1, [-1]];
const lowerIndexCheck = (nowScoreBoard) => {
        if(maxScore[1][10] === undefined) return true;

        for(let i=10; i>=0; i--) {
            if(nowScoreBoard[i] > maxScore[1][i]) return true;
            else if(nowScoreBoard[i] < maxScore[1][i]) return false;
        }   
    }
    
const recursion = (idx, n, scoreBoard) => {
	// 기저조건
	if(idx === 10 || n === 0 ) {
	// maxScore에 있는 값과 비교해서 동일할 때 아닐 때 분기처리
    		// 만약에 n이 남았다면 맨 끝에다가 넣어주기
            // 가장 작은 점수를 맞춘 점수가 높아야하므로
            // 이미 점수가 결정난 상태라면 맨 끝에 투자해주는 것이 맞다.
            scoreBoard[10] = n;
            var aScore = 0;
            var bScore = 0;
            // 라이언과 어피치의 점수를 계산하는 로직
            for(let i=0;i<=10;i++) {
                if(info[i] < scoreBoard[i]) bScore += 10-i;
                else if(info[i] > 0) aScore += 10-i;
            }
            // 만약 라이언이 어피치 점수보다 높고(초과), 현재 점수차가 이전에 담아두었던 점수차보다 크다면 
            if(bScore > aScore && bScore-aScore > maxScore[0]) {
            	// 그대로 정답을 갱신해주면 된다.
                maxScore[0] = bScore-aScore;
                maxScore[1] = [...scoreBoard];
            } else if(bScore > aScore && bScore-aScore === maxScore[0] && lowerIndexCheck(scoreBoard)){
            	// 하지만 만약에 이전 점수차와 같다면 lowerIndexCheck라는 함수를 통해 아래값부터 비교해서 이전에 쌓인 기록이 더욱크면 false, 지금 쌓아놓은 기록이 더욱 크면 true를 리턴하도록 한다.
                maxScore[0] = bScore-aScore;
                maxScore[1] = [...scoreBoard];
            }
            // 마지막에 다시 값을 0으로 해놓고 리턴한다.
            scoreBoard[10] = 0;
            return; 
	}
}

• 분기처리 로직 : n이 어피치가 특정 점수대에서 맞춘 화살의 개수보다 많다면 라이언이 이길수 있는 케이스이기에 어피치가 맞춘 개수 +1 만큼 n에서 차감하고 라이언이 맞춘 점수를 담는 배열에 담는다. 그리고 다음 재귀 로직으로 넘어가되 idx++을 해준다. 그럼 그 다음 재귀함수에서도 똑같은 시행을 하는데, 다시 분기처리로 돌아와서 만약 n이 어피치가 맞춘 화살의 개수보다 적게 남았다면(혹은 같다면) 라이언이 못이기는 상황이기에 n을 투자하지 않고 idx++만 해주고 넘어간다(다음 재귀함수로) 그렇게 쭉 기저조건에 닿을때까지 진행한다.
• 위의 분기처리 로직대로 진행하고 기저조건에 닿고, return을 하면 이전 시행으로 돌아온 다음에
  - 만약 이전 로직에서 라이언이 이길 수 있는 상황이었다면 다시 돌아와서(재귀함수로부터) idx--, scoreBoard에 추가했던 라이언이 맞춘 화살개수를 다시 되돌리는 작업 후에 다시 어피치가 이기는 케이스로 간다.
  

    const recursion = (idx, n, scoreBoard) => {
        if(idx === 10 || n === 0) {
            scoreBoard[10] = n;
            var aScore = 0;
            var bScore = 0;
            for(let i=0;i<=10;i++) {
                if(info[i] < scoreBoard[i]) bScore += 10-i;
                else if(info[i] > 0) aScore += 10-i;
            }
            if(bScore > aScore && bScore-aScore > maxScore[0]) {
                maxScore[0] = bScore-aScore;
                maxScore[1] = [...scoreBoard];
            } else if(bScore > aScore && bScore-aScore === maxScore[0] && lowerIndexCheck(scoreBoard)){
                maxScore[0] = bScore-aScore;
                maxScore[1] = [...scoreBoard];
            }
            scoreBoard[10] = 0;
            return; 
        } else {
        	// 만약에 라이언이 쏠 수 있는 화살 개수 n이 어피치를 이길 수 있는 상황이라면 
            if(info[idx] < n) {
            	// 라이언의 scoreBoard 배열에 어피치를 이길 수 있는 만큼의 화살을 투자하도록 하고 다음 재귀함수에서 사용할 n에서 사용한 만큼을 차감해서 인자로 넣어준다. 
                scoreBoard[idx] += info[idx]+1;
                recursion(idx+1, n-info[idx]-1, scoreBoard);
                // 재귀함수를 끝내고 돌아온 경우 다시 scoreBoard를 원상태로 만들어준다.
                scoreBoard[idx] = 0;
            }
            // if문을 벗어났을 떄는 이제 해당 점수대에서 라이언이 지는 케이스를 바탕으로 재귀함수를 돌려준다. 
            recursion(idx+1, n, scoreBoard);
        }
    }

이렇게 마무리를 해준다.

최종 풀이 코드

function solution(n, info) {
    var scoreBoard = Array.from({length: 11}, (v) => 0);
    var maxScore = [-1, [-1]];
    
    const lowerIndexCheck = (nowScoreBoard) => {
        if(maxScore[1][10] === undefined) return true;
        
        for(let i=10; i>=0; i--) {
            if(nowScoreBoard[i] > maxScore[1][i]) return true;
            else if(nowScoreBoard[i] < maxScore[1][i]) return false;
        }   
    }
    
    const recursion = (idx, n, scoreBoard) => {
        if(idx === 10 || n === 0) {
            scoreBoard[10] = n;
            var aScore = 0;
            var bScore = 0;
            for(let i=0;i<=10;i++) {
                if(info[i] < scoreBoard[i]) bScore += 10-i;
                else if(info[i] > 0) aScore += 10-i;
            }
            if(bScore > aScore && bScore-aScore > maxScore[0]) {
                maxScore[0] = bScore-aScore;
                maxScore[1] = [...scoreBoard];
            } else if(bScore > aScore && bScore-aScore === maxScore[0] && lowerIndexCheck(scoreBoard)){
                maxScore[0] = bScore-aScore;
                maxScore[1] = [...scoreBoard];
            }
            scoreBoard[10] = 0;
            return; 
        } else {
            if(info[idx] < n) {
                scoreBoard[idx] += info[idx]+1;
                recursion(idx+1, n-info[idx]-1, scoreBoard);
                scoreBoard[idx] = 0;
            }
            
            recursion(idx+1, n, scoreBoard);
        }
    }
    recursion(0, n, scoreBoard);
    return maxScore[1];
}