코딩 테스트/Level 2
[2022 KAKAO BLIND RECRUITMENT] 양궁대회
컴닥
2022. 1. 18. 22:46
반응형
https://programmers.co.kr/learn/courses/30/lessons/92342
코딩테스트 연습 - 양궁대회
문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원
programmers.co.kr
무지성 코딩을 하면...
def get_point(a_shots, l_shots, areal_point):
a_score, l_score = 0, 0
if l_shots > a_shots:
l_score = areal_point
elif a_shots > 0:
a_score = areal_point
return a_score, l_score
def solution(n, info):
answers = {}
lion_max = 0
total = [(0, 0)] * 11
for i10 in range(info[0] + 1, -1, -1):
if i10 > n:
continue
total[0] = get_point(info[0], i10, 10)
for i9 in range(info[1] + 1, -1, -1):
if i9 + i10 > n:
continue
total[1] = get_point(info[1], i9, 9)
for i8 in range(info[2] + 1, -1, -1):
if i8 + i9 + i10 > n:
continue
total[2] = get_point(info[2], i8, 8)
for i7 in range(info[3] + 1, -1, -1):
if i7 + i8 + i9 + i10 > n:
continue
total[3] = get_point(info[3], i7, 7)
for i6 in range(info[4] + 1, -1, -1):
if i6 + i7 + i8 + i9 + i10 > n:
continue
total[4] = get_point(info[4], i6, 6)
for i5 in range(info[5] + 1, -1, -1):
if i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[5] = get_point(info[5], i5, 5)
for i4 in range(info[6] + 1, -1, -1):
if i4 + i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[6] = get_point(info[6], i4, 4)
for i3 in range(info[7] + 1, -1, -1):
if i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[7] = get_point(info[7], i3, 3)
for i2 in range(info[8] + 1, -1, -1):
if i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[8] = get_point(info[8], i2, 2)
for i1 in range(info[9] + 1, -1, -1):
if i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[9] = get_point(info[9], i1, 1)
for i0 in range(info[10] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[10] = get_point(info[10], i0, 0)
a_total = l_total = 0
for a_point, l_point in total:
a_total += a_point
l_total += l_point
if l_total > a_total:
temp = l_total - a_total
if lion_max <= temp:
lion_max = temp
answers.setdefault(temp, [])
answers[temp].append(
(i10, i9, i8, i7, i6, i5, i4, i3, i2, i1, i0))
return sorted(answers[lion_max],
key=lambda x: (x[10], x[9], x[8], x[7], x[6], x[5], x[4], x[3], x[2], x[1], x[0])
)[-1] if lion_max > 0 else [-1]빠름...
테스트 1 〉 통과 (0.22ms, 10.3MB)
테스트 2 〉 통과 (39.29ms, 10.3MB)
테스트 3 〉 통과 (40.60ms, 10.4MB)
테스트 4 〉 통과 (3.94ms, 10.3MB)
테스트 5 〉 통과 (69.02ms, 10.2MB)
테스트 6 〉 통과 (70.05ms, 10.3MB)
테스트 7 〉 통과 (7.42ms, 10.4MB)
테스트 8 〉 통과 (1.00ms, 10.4MB)
테스트 9 〉 통과 (3.90ms, 10.3MB)
테스트 10 〉 통과 (0.67ms, 10.3MB)
테스트 11 〉 통과 (1.95ms, 10.4MB)
테스트 12 〉 통과 (1.78ms, 10.3MB)
테스트 13 〉 통과 (12.24ms, 10.3MB)
테스트 14 〉 통과 (53.61ms, 10.3MB)
테스트 15 〉 통과 (43.29ms, 10.3MB)
테스트 16 〉 통과 (8.28ms, 10.4MB)
테스트 17 〉 통과 (3.88ms, 10.3MB)
테스트 18 〉 통과 (0.24ms, 10.3MB)
테스트 19 〉 통과 (0.06ms, 10.3MB)
테스트 20 〉 통과 (41.17ms, 10.4MB)
테스트 21 〉 통과 (45.21ms, 10.2MB)
테스트 22 〉 통과 (70.27ms, 10.3MB)
테스트 23 〉 통과 (0.68ms, 10.4MB)
테스트 24 〉 통과 (23.87ms, 10.4MB)
테스트 25 〉 통과 (15.32ms, 10.2MB)def get_point(a_shots, l_shots, areal_point):
a_score, l_score = 0, 0
if l_shots > a_shots:
l_score = areal_point
elif a_shots > 0:
a_score = areal_point
return a_score, l_score
def solution(n, info):
answer = []
lion_max = 0
total = [(0, 0)] * 11
for i0 in range(info[10] + 1, -1, -1):
if i0 > n:
continue
total[10] = get_point(info[10], i0, 0)
for i1 in range(info[9] + 1, -1, -1):
if i0 + i1 > n:
continue
total[9] = get_point(info[9], i1, 1)
for i2 in range(info[8] + 1, -1, -1):
if i0 + i1 + i2 > n:
continue
total[8] = get_point(info[8], i2, 2)
for i3 in range(info[7] + 1, -1, -1):
if i0 + i1 + i2 + i3 > n:
continue
total[7] = get_point(info[7], i3, 3)
for i4 in range(info[6] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 > n:
continue
total[6] = get_point(info[6], i4, 4)
for i5 in range(info[5] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 > n:
continue
total[5] = get_point(info[5], i5, 5)
for i6 in range(info[4] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 + i6 > n:
continue
total[4] = get_point(info[4], i6, 6)
for i7 in range(info[3] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 + i6 + i7 > n:
continue
total[3] = get_point(info[3], i7, 7)
for i8 in range(info[2] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 + i6 + i7 > n:
continue
total[2] = get_point(info[2], i8, 8)
for i9 in range(info[1] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 > n:
continue
total[1] = get_point(info[1], i9, 9)
for i10 in range(info[0] + 1, -1, -1):
if i0 + i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 + i10 > n:
continue
total[0] = get_point(info[0], i10, 10)
a_total = l_total = 0
for a_point, l_point in total:
a_total += a_point
l_total += l_point
if l_total > a_total:
temp = l_total - a_total
if lion_max < temp:
lion_max = temp
answer = [i10, i9, i8, i7, i6, i5, i4, i3, i2, i1, i0]
return answer if lion_max > 0 else [-1]약간 더 느림.
테스트 1 〉 통과 (0.40ms, 10.2MB)
테스트 2 〉 통과 (54.65ms, 10.4MB)
테스트 3 〉 통과 (82.02ms, 10.2MB)
테스트 4 〉 통과 (7.57ms, 10.4MB)
테스트 5 〉 통과 (78.66ms, 10.4MB)
테스트 6 〉 통과 (82.14ms, 10.2MB)
테스트 7 〉 통과 (4.83ms, 10.2MB)
테스트 8 〉 통과 (0.80ms, 10.4MB)
테스트 9 〉 통과 (3.58ms, 10.1MB)
테스트 10 〉 통과 (1.55ms, 10.3MB)
테스트 11 〉 통과 (3.42ms, 10.3MB)
테스트 12 〉 통과 (2.99ms, 10.3MB)
테스트 13 〉 통과 (19.09ms, 10.3MB)
테스트 14 〉 통과 (50.81ms, 10.3MB)
테스트 15 〉 통과 (54.81ms, 10.1MB)
테스트 16 〉 통과 (14.76ms, 10.2MB)
테스트 17 〉 통과 (5.29ms, 10.3MB)
테스트 18 〉 통과 (0.25ms, 10.3MB)
테스트 19 〉 통과 (0.06ms, 10.2MB)
테스트 20 〉 통과 (80.04ms, 10.4MB)
테스트 21 〉 통과 (45.31ms, 10.3MB)
테스트 22 〉 통과 (78.37ms, 10.3MB)
테스트 23 〉 통과 (0.79ms, 10.3MB)
테스트 24 〉 통과 (38.19ms, 10.2MB)
테스트 25 〉 통과 (20.97ms, 10.3MB)
무지성 재귀로 풀어보았습니다.
def solution(n, info):
def get_areal_score(areal_point, a_shots, l_shots):
a_areal_score, l_areal_score = 0, 0
if l_shots > a_shots:
l_areal_score = areal_point
elif a_shots > 0:
a_areal_score = areal_point
return a_areal_score, l_areal_score
def get_total_score(a_scores, l_scores):
a_total, l_total = 0, 0
for index, (a_shots, l_shots) in enumerate(zip(a_scores, l_scores)):
a_areal_score, l_areal_score = get_areal_score(10 - index, a_shots, l_shots)
a_total += a_areal_score
l_total += l_areal_score
return a_total, l_total
def recursive(l_scores, shots):
nonlocal answers, l_max
if shots > n:
return
if len(l_scores) == 11:
if shots == n:
a_score, l_score = get_total_score(info, l_scores)
if (diff := l_score - a_score) >= l_max:
l_max = diff
answers.setdefault(diff, [])
answers[diff].append(l_scores)
return
for each in range(n + 1):
recursive(l_scores + [each], shots + each)
l_max = 0
answers = {}
recursive([], 0)
return sorted(answers[l_max],
key=lambda x: (x[10], x[9], x[8], x[7], x[6], x[5], x[4], x[3], x[2], x[1], x[0])
)[-1] if l_max > 0 else [-1]매우 느림
테스트 1 〉 통과 (0.82ms, 10.3MB)
테스트 2 〉 통과 (873.48ms, 10.4MB)
테스트 3 〉 통과 (699.37ms, 10.2MB)
테스트 4 〉 통과 (19.63ms, 10.2MB)
테스트 5 〉 통과 (1435.51ms, 10.2MB)
테스트 6 〉 통과 (1511.51ms, 10.4MB)
테스트 7 〉 통과 (19.89ms, 10.2MB)
테스트 8 〉 통과 (3.50ms, 10.2MB)
테스트 9 〉 통과 (19.62ms, 10.2MB)
테스트 10 〉 통과 (3.42ms, 10.3MB)
테스트 11 〉 통과 (6.86ms, 10.4MB)
테스트 12 〉 통과 (6.59ms, 10.3MB)
테스트 13 〉 통과 (153.43ms, 10.3MB)
테스트 14 〉 통과 (755.76ms, 10.3MB)
테스트 15 〉 통과 (760.29ms, 10.2MB)
테스트 16 〉 통과 (68.59ms, 10.2MB)
테스트 17 〉 통과 (26.18ms, 10.2MB)
테스트 18 〉 통과 (0.46ms, 10.3MB)
테스트 19 〉 통과 (0.15ms, 10.3MB)
테스트 20 〉 통과 (671.60ms, 10.3MB)
테스트 21 〉 통과 (794.79ms, 10.2MB)
테스트 22 〉 통과 (1380.11ms, 10.2MB)
테스트 23 〉 통과 (3.43ms, 10.3MB)
테스트 24 〉 통과 (1338.82ms, 10.3MB)
테스트 25 〉 통과 (1334.11ms, 10.4MB)...
def solution(n, a_scores):
def get_score(r_scores):
total = 0
for i in range(11):
if r_scores[i] > a_scores[i]:
total += 10 - i
elif a_scores[i] > 0:
total -= 10 - i
return total
def recursive(index, left_shot, r_scores):
nonlocal answer, max_score
if index == -1 and left_shot:
return
if left_shot == 0:
score = get_score(r_scores)
if max_score < score:
answer = r_scores.copy()
max_score = score
return
for i in range(left_shot, -1, -1):
r_scores[index] = i
recursive(index - 1, left_shot - i, r_scores)
r_scores[index] = 0
max_score = 0
answer = [0 for _ in range(11)]
recursive(10, n, [0 for _ in range(11)])
return [-1] if max_score == 0 else answer테스트 1 〉 통과 (0.13ms, 10.1MB)
테스트 2 〉 통과 (198.61ms, 10.2MB)
테스트 3 〉 통과 (190.46ms, 10.2MB)
테스트 4 〉 통과 (5.88ms, 10.2MB)
테스트 5 〉 통과 (396.61ms, 10.2MB)
테스트 6 〉 통과 (400.44ms, 10.3MB)
테스트 7 〉 통과 (5.91ms, 10.3MB)
테스트 8 〉 통과 (0.56ms, 10.3MB)
테스트 9 〉 통과 (5.92ms, 10MB)
테스트 10 〉 통과 (0.58ms, 10.1MB)
테스트 11 〉 통과 (1.95ms, 10.3MB)
테스트 12 〉 통과 (4.00ms, 10MB)
테스트 13 〉 통과 (44.37ms, 10.1MB)
테스트 14 〉 통과 (226.66ms, 10.2MB)
테스트 15 〉 통과 (191.86ms, 10.2MB)
테스트 16 〉 통과 (16.30ms, 10.2MB)
테스트 17 〉 통과 (6.39ms, 10.4MB)
테스트 18 〉 통과 (0.13ms, 10.2MB)
테스트 19 〉 통과 (0.04ms, 10MB)
테스트 20 〉 통과 (188.35ms, 10.2MB)
테스트 21 〉 통과 (193.99ms, 10.2MB)
테스트 22 〉 통과 (450.45ms, 10.2MB)
테스트 23 〉 통과 (0.58ms, 10.2MB)
테스트 24 〉 통과 (367.64ms, 10.2MB)
테스트 25 〉 통과 (351.31ms, 10MB)
자바
class Solution {
int max_score = 0;
int[] a_scores;
int[] answer = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int get_score(int[] r_scores) {
int total = 0;
for (var i = 0; i < 11; i++) {
if (r_scores[i] > a_scores[i])
total += 10 - i;
else if (a_scores[i] > 0)
total -= 10 - i;
}
return total;
}
void recursive(int index, int left_shot, int[] r_scores) {
if (index == -1 && left_shot > 0) {
return;
}
if (left_shot == 0) {
var score = get_score(r_scores);
if (max_score < score) {
answer = r_scores.clone();
max_score = score;
}
return;
}
for (var i = left_shot; i > -1; i--) {
r_scores[index] = i;
recursive(index - 1, left_shot - i, r_scores);
r_scores[index] = 0;
}
}
public int[] solution(int n, int[] info) {
a_scores = info;
recursive(10, n, new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
return (max_score == 0) ? new int[]{-1} : answer;
}
}테스트 1 〉 통과 (0.06ms, 72.6MB)
테스트 2 〉 통과 (8.59ms, 74MB)
테스트 3 〉 통과 (5.27ms, 78.4MB)
테스트 4 〉 통과 (0.68ms, 83.5MB)
테스트 5 〉 통과 (11.95ms, 78.7MB)
테스트 6 〉 통과 (10.15ms, 85.2MB)
테스트 7 〉 통과 (0.82ms, 76.7MB)
테스트 8 〉 통과 (0.32ms, 75.7MB)
테스트 9 〉 통과 (0.68ms, 76.9MB)
테스트 10 〉 통과 (0.34ms, 72.2MB)
테스트 11 〉 통과 (0.53ms, 74.4MB)
테스트 12 〉 통과 (0.47ms, 72.2MB)
테스트 13 〉 통과 (2.16ms, 75.1MB)
테스트 14 〉 통과 (7.71ms, 78.1MB)
테스트 15 〉 통과 (8.65ms, 83MB)
테스트 16 〉 통과 (2.03ms, 79.5MB)
테스트 17 〉 통과 (0.79ms, 76.7MB)
테스트 18 〉 통과 (0.08ms, 85.3MB)
테스트 19 〉 통과 (0.04ms, 76.6MB)
테스트 20 〉 통과 (5.77ms, 74.4MB)
테스트 21 〉 통과 (6.20ms, 81.8MB)
테스트 22 〉 통과 (10.90ms, 83.7MB)
테스트 23 〉 통과 (0.36ms, 84.1MB)
테스트 24 〉 통과 (10.53ms, 76.1MB)
테스트 25 〉 통과 (11.06ms, 76.9MB)반응형