상대보다 많은 화살을 맞히며, 점수를 빼앗아오는 문제.
어피치의 점수를 class 내에 선언하여 계산하는 방식으로 풀었다. 재귀함수로 넘기는 게 더 깔끔한 코드가 나왔을 것 같다.
class Solution {
private int[] info;
private int[] log = new int[11];
private int[] bestLog = new int[11];
private int bestScore = 0;
private int enemyScore = 0;
public void getScore(int score, int arrow, int step) {
if (step == 10) {
log[10] = arrow;
if (score - enemyScore < bestScore)
return;
if (score - enemyScore > bestScore) {
bestScore = score - enemyScore;
bestLog = log.clone();
return;
}
for (int i = 10; i >= 0; i--) {
if (log[i] == bestLog[i])
continue;
else if (log[i] > bestLog[i])
bestLog = log.clone();
return;
}
}
if (arrow > info[step]) {
log[step] = info[step] + 1;
enemyScore -= info[step] > 0 ? 10 - step : 0;
getScore(score + 10 - step, arrow - info[step] - 1, step + 1);
log[step] = 0;
enemyScore += info[step] > 0 ? 10 - step : 0;
}
getScore(score, arrow, step + 1);
}
public int[] solution(int n, int[] info) {
this.info = info;
for (int i = 0; i < 10; i++)
if (info[i] > 0)
enemyScore += 10 - i;
getScore(0, n, 0);
return bestScore > 0 ? bestLog : new int[] {-1};
}
}
this.info = info;
for (int i = 0; i < 10; i++)
if (info[i] > 0)
enemyScore += 10 - i;
getScore(0, n, 0);
return bestScore > 0 ? bestLog : new int[] {-1};
어피치의 점수를 미리 계산, getScore 재귀함수를 돌리고 bestScore가 존재한다면 bestLog 배열을, 아니라면 [-1]을 반환하도록 했다.
...
if (arrow > info[step]) {
log[step] = info[step] + 1;
enemyScore -= info[step] > 0 ? 10 - step : 0;
getScore(score + 10 - step, arrow - info[step] - 1, step + 1);
log[step] = 0;
enemyScore += info[step] > 0 ? 10 - step : 0;
}
getScore(score, arrow, step + 1);
내가 가진 화살의 수가 어피치의 X점에 맞힌 화살보다 많다면, 해당 점수를 어피치에게 뺏어올 수 있다. 따라서 내가 점수를 맞힌 기록인 log에 어피치보다 1발 더 많게 작성한다.
어피치가 X점에 1발 이상 맞혔던 경우, X점을 뺏어온다. 맞추지 못 했던 경우, 내 점수만 올리면 된다.
기존 점수 + X점, 화살 갯수, 재귀 횟수를 계산하고 다음 재귀함수를 실행시킨다.
재귀함수에서 벗어났을 경우, log와 enemyScore을 직전 상태로 변환.
화살을 사용하지 않고 다음 재귀함수를 호출한다.
if (step == 10) {
log[10] = arrow;
if (score - enemyScore < bestScore)
return;
if (score - enemyScore > bestScore) {
bestScore = score - enemyScore;
bestLog = log.clone();
return;
}
for (int i = 10; i >= 0; i--) {
if (log[i] == bestLog[i])
continue;
else if (log[i] > bestLog[i])
bestLog = log.clone();
return;
}
}
재귀를 10번 다 돌았을 경우, 0점 기록에 남은 화살을 다 넣는다.
만약 내 점수 - 어피치의 점수가 bestScore를 넘기지 못 했을 경우, 그냥 반환.
bestScore를 갱신했다면 현재 화살 맞춘 log를 기록.
bestScore가 똑같다면, 문제에서 주어진 조건을 따른다.
라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
화살은 최대 10개까지 지닐 수 있고, 어피치가 한 점수에 9, 10개를 맞춘 경우는 만들어질 수 있는 경우의 수가 얼마 되지 않기 때문에 int형으로 점수를 쌓아도 문제가 없다. 그러나 처음에 주어지는 n이 상당히 많아질 경우, 해당 알고리즘은 수정이 불가피하다. 즉, 좋은 풀이는 아니다.
def solution(n, info):
score = 0
for i in range(10):
score += 10 - i if info[i] else 0
min_log = 99999999999
max_val = -60
def shoot(arrow, apeach, ryan=0, idx=0, log=0):
if idx == 10:
nonlocal min_log, max_val
log = log * 10 + arrow
if max_val < ryan - apeach:
max_val = ryan - apeach
min_log = log
elif max_val == ryan - apeach:
for i in range(10):
A = min_log % 10 ** i
B = log % 10 ** i
if A < B:
min_log = log
return
elif A > B:
return
return
if arrow > info[idx] and arrow - info[idx] - 1 >= 0:
shoot(arrow - info[idx] - 1, apeach - (10 - idx if info[idx] else 0), ryan + (10 - idx), idx + 1, log * 10 + info[idx] + 1)
shoot(arrow, apeach, ryan, idx + 1, log * 10)
shoot(n, score)
if max_val <= 0:
return [-1]
min_log = list(map(int, str(min_log)))
return [0] * (11 - len(min_log)) + min_log
score = 0
for i in range(10):
score += 10 - i if info[i] else 0
min_log = 99999999999
max_val = -60
어피치 점수 계산.
def shoot(arrow, apeach, ryan=0, idx=0, log=0):
if idx == 10:
nonlocal min_log, max_val
log = log * 10 + arrow
if max_val < ryan - apeach:
max_val = ryan - apeach
min_log = log
elif max_val == ryan - apeach:
for i in range(10):
A = min_log % 10 ** i
B = log % 10 ** i
if A < B:
min_log = log
return
elif A > B:
return
return
if arrow > info[idx] and arrow - info[idx] - 1 >= 0:
shoot(arrow - info[idx] - 1, apeach - (10 - idx if info[idx] else 0), ryan + (10 - idx), idx + 1, log * 10 + info[idx] + 1)
shoot(arrow, apeach, ryan, idx + 1, log * 10)
화살이 어피치의 X점 맞춘 횟수보다 많은 경우, 화살을 어피치보다 1회 더 많이 맞췄을 때와 그렇지 않을 때로 나눠 재귀를 돌린다.
재귀를 다 돌렸을 경우, log를 살펴보며 가장 낮은 점수를 더 많이 맞힌 경우를 찾는다.
shoot(n, score)
if max_val <= 0:
return [-1]
min_log = list(map(int, str(min_log)))
return [0] * (11 - len(min_log)) + min_log
재귀함수 호출, 최고값이 0 이하일 경우 [-1] 반환, 아니라면 기록값을 숫자 하나씩 나눠 앞에 0 붙이고 반환.
N = 100
, info = [90, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0]
이 주어질 경우, Python 풀이 같은 경우엔 [91, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
이 아닌 [9, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
이 반환된다.
비록 답은 맞지만, 그래도 어떤 풀이가 더 옳은지 생각해보자.