카카오배 양궁대회가 열렸습니다.
라이언
은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치
입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.
n
발을 다 쏜 후에 라이언이 화살 n
발을 쏩니다.현재 상황은 어피치가 화살 n
발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n
발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.
화살의 개수를 담은 자연수 n
, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info
가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n
발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]
을 return 해주세요.
n
≤ 10info
의 길이 = 11
info
의 원소 ≤ n
info
의 원소 총합 = n
info
의 i번째 원소는 과녁의 10 - i
점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)n
n
(꼭 n발을 다 쏴야 합니다.)10 - i
점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)[2,3,1,0,0,0,0,1,3,0,0]
과 [2,1,0,2,0,0,0,2,3,0,0]
를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]
를 return 해야 합니다.[0,0,2,3,4,1,0,0,0,0,0]
과 [9,0,0,0,0,0,0,0,1,0,0]
를 비교하면[9,0,0,0,0,0,0,0,1,0,0]
를 return 해야 합니다.[-1]
을 return 해야 합니다.n | info | result |
---|---|---|
5 | [2,1,1,1,0,0,0,0,0,0,0] | [0,2,2,0,1,0,0,0,0,0,0] |
1 | [1,0,0,0,0,0,0,0,0,0,0] | [-1] |
9 | [0,0,1,2,0,1,1,1,1,1,1] | [1,1,2,0,1,2,2,0,0,0,0] |
10 | [0,0,0,0,0,0,0,0,3,4,3] | [1,1,1,1,1,1,1,1,0,0,2] |
입출력 예 #1
어피치와 라이언이 아래와 같이 화살을 맞힐 경우,
과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
---|---|---|---|
10 | 2 | 3 | 라이언이 10점 획득 |
9 | 1 | 2 | 라이언이 9점 획득 |
8 | 1 | 0 | 어피치가 8점 획득 |
7 | 1 | 0 | 어피치가 7점 획득 |
6 | 0 | 0 | |
5 | 0 | 0 | |
4 | 0 | 0 | |
3 | 0 | 0 | |
2 | 0 | 0 | |
1 | 0 | 0 | |
0 | 0 | 0 |
어피치의 최종 점수는 15점, 라이언의 최종 점수는 19점입니다. 4점 차이로 라이언이 우승합니다.
하지만, 라이언이 아래와 같이 화살을 맞힐 경우 더 큰 점수 차로 우승할 수 있습니다.
과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
---|---|---|---|
10 | 2 | 0 | 어피치가 10점 획득 |
9 | 1 | 2 | 라이언이 9점 획득 |
8 | 1 | 2 | 라이언이 8점 획득 |
7 | 1 | 0 | 어피치가 7점 획득 |
6 | 0 | 1 | 라이언이 6점 획득 |
5 | 0 | 0 | |
4 | 0 | 0 | |
3 | 0 | 0 | |
2 | 0 | 0 | |
1 | 0 | 0 | |
0 | 0 | 0 |
어피치의 최종 점수는 17점, 라이언의 최종 점수는 23점입니다. 6점 차이로 라이언이 우승합니다.
따라서 [0,2,2,0,1,0,0,0,0,0,0]
을 return 해야 합니다.
입출력 예 #2
라이언이 10점을 맞혀도 어피치가 10점을 가져가게 됩니다.
따라서, 라이언은 우승할 수 없기 때문에 [-1]
을 return 해야 합니다.
입출력 예 #3
어피치와 라이언이 아래와 같이 화살을 맞힐 경우,
과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
---|---|---|---|
10 | 0 | 1 | 라이언이 10점 획득 |
9 | 0 | 1 | 라이언이 9점 획득 |
8 | 1 | 2 | 라이언이 8점 획득 |
7 | 2 | 3 | 라이언이 7점 획득 |
6 | 0 | 0 | |
5 | 1 | 2 | 라이언이 5점 획득 |
4 | 1 | 0 | 어피치가 4점 획득 |
3 | 1 | 0 | 어피치가 3점 획득 |
2 | 1 | 0 | 어피치가 2점 획득 |
1 | 1 | 0 | 어피치가 1점 획득 |
0 | 1 | 0 | 어피치가 0점 획득 |
어피치의 최종 점수는 10점, 라이언의 최종 점수는 39점입니다. 29점 차이로 라이언이 우승합니다.
하지만 라이언이 아래와 같이 화살을 맞힐 경우,
과녁 점수 | 어피치가 맞힌 화살 개수 | 라이언이 맞힌 화살 개수 | 결과 |
---|---|---|---|
10 | 0 | 1 | 라이언이 10점 획득 |
9 | 0 | 1 | 라이언이 9점 획득 |
8 | 1 | 2 | 라이언이 8점 획득 |
7 | 2 | 0 | 어피치가 7점 획득 |
6 | 0 | 1 | 라이언이 6점 획득 |
5 | 1 | 2 | 라이언이 5점 획득 |
4 | 1 | 2 | 라이언이 4점 획득 |
3 | 1 | 0 | 어피치가 3점 획득 |
2 | 1 | 0 | 어피치가 2점 획득 |
1 | 1 | 0 | 어피치가 1점 획득 |
0 | 1 | 0 | 어피치가 0점 획득 |
어피치의 최종 점수는 13점, 라이언의 최종 점수는 42점입니다. 이 경우도 29점 차이로 라이언이 우승합니다.
하지만, 첫 번째 경우와 두 번째 경우를 비교했을 때, 두 번째 경우가 두 경우 중 가장 낮은 점수인 4점을 더 많이 맞혔기 때문에 [1,1,2,3,0,2,0,0,0,0,0]
이 아닌 [1,1,2,0,1,2,2,0,0,0,0]
을 return 해야 합니다.
입출력 예 #4
가장 큰 점수 차이로 이기는 경우 중에서 가장 낮은 점수를 가장 많이 맞힌, 10~3점을 한 발씩 맞히고 나머지 두 발을 0점에 맞히는 경우인 [1,1,1,1,1,1,1,1,0,0,2]
를 return 해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
이 문제는 아래 함수를 만들어서 푼다.
input: apeachCount,ryanCount, usedShotCount, point, arr
1. apeachCount: 어피치가 얻은 점수
2. ryanCount: 라이언이 얻은 점수
3.usedShotCount: 현재 라이언이 쏜 화살 수
4. point: 지금 몇점을 기준으로 하고 있는지
5. arr: 라이언이 쏜 점수 배열
1) point>10이라면 => point가 0부터 10까지 다 순회하고 왔다면 아래과정을 시행
라이언의 점수와 어피치 점수 차이를 구함.
이 차이가 최대 차이보다 크다면 최대차이를 변경
또한 마지막에 배열에 아직 쏘지 않고 남은 값을 추가
answer=현재 만든 배열로 변경
2) 만약 라이언이 이긴다면?
새로운 배열을 따로 만들고, 거기게 어피치 점수에 해당하는 값에 1만큼 높은 값으로 변경해주고 그 값을 함수에 다시 넣어준다. (재귀)
-> 재귀 인자: apeachCount,ryanCount + point, usedShotCount + info[10-point] + 1, point+1,current
그대로, 라이언이 점수획득, 어피치가 그 point에 해당하는 영역에 쏜 것보다 1만큼 크게 쏜다, 다음 포인터로 이동, 바꿔준 배열
3) 어피치가 이긴 경우
단, 어피치의 값이 0은 아니여야 한다. 재귀 실행
인자: apeachCount+point,ryanCount,usedShotCount,point+1,arr
-> 어피치에 점수 추가하고 다음 포인터로 이동
4) 둘다 점수를 얻지 못한 상황 => 둘다 0점인 경우
다음 포인터로 이동하는 재귀 실행
- 위의 함수에 초기값 0,0,0,0,answer을 넣어줌으로써 answer을 구함.
단, 여기서 maxDif가 한번도 바뀌지 않은 초기값 0이라면 [-1]을 리턴
아니라면 answer을 리턴
function solution(n, info) {
//라이언이 어떻게 쏠지에 대한 answer 배열
var answer= new Array(11).fill(0);
var maxDif = 0;
function shootRyan(apeachCount,ryanCount, usedShotCount, point, arr){
// 화살수가 이미 n을 넘었다면 패스
if(n<usedShotCount)return;
// 한바퀴를 돌았다면 값들을 체크
if(point>10){
// 둘의 점수를 체크
var dif = ryanCount - apeachCount;
//max보다 크다면
if(maxDif<dif){
//아직 못쏜 값은 마지막에 쏜다.
arr[10] = n-usedShotCount;
maxDif = dif;
answer = arr;
}
return;
}
//라이언이 이길때
if(n>usedShotCount){
// 기존 arr을 받음
var current = [...arr];
// point에 해당하는 배열에 인덱스를 1추가
current[10 - point] = info[10-point] + 1;
// 라이언이 10-point번째 점수를 얻기 위해선 info에 해당하는 값보다 1은 커야 됌. 그만큼을 쏜다고 가정
shootRyan(apeachCount,ryanCount + point, usedShotCount + info[10-point] + 1, point+1,current);
};
//어피치가 이기는 경우
if(info[10-point]>0){
// 어피치 점수에 point만큼을 더해주고 다음 포인터로 이동
shootRyan(apeachCount+point,ryanCount,usedShotCount,point+1,arr);
}
else{
//둘다 점수를 못얻는 상황: 둘다 0,0 번씩 쏜 경우는 다음 point로만 이동
shootRyan(apeachCount,ryanCount,usedShotCount,point+1,arr);
}
}
shootRyan(0,0,0,0,answer);
if(maxDif===0){
return [-1];
}
else{
return answer;
}
}