https://school.programmers.co.kr/learn/courses/30/lessons/92342
1. 중복 조합 풀이
from collections import defaultdict
from itertools import combinations_with_replacement
def solution(n, info):
def update_answer(a, b):
return a[::-1] > b[::-1]
def calculate_score(ryan):
apeach_score = 0
ryan_score = 0
for i in range(11):
if info[i] == ryan[i] == 0:
continue
elif info[i] >= ryan[i]:
apeach_score += abs(i - 10)
else:
ryan_score += abs(i - 10)
if ryan_score > apeach_score:
if max_value[0] == ryan_score - apeach_score:
if not update_answer(answer[0], ryan):
answer.clear()
answer.append(ryan)
elif max_value[0] < ryan_score - apeach_score:
max_value[0] = ryan_score - apeach_score
answer.clear()
answer.append(ryan)
max_value = [-1]
answer = []
for arrows in combinations_with_replacement([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], n):
result = [0] * 11
for arrow in arrows:
result[10 - arrow] += 1
calculate_score(result)
if len(answer) == 0:
return [-1]
else:
return answer[0]2. DFS 풀이
""" DFS(10-i점 탐색, 남은 화살 수, Ryan 점수판)"""
def solution(n, info):
def update_answer(a, b):
return a[::-1] > b[::-1]
def calculate_score(ryan):
apeach_score = 0
ryan_score = 0
for i in range(11):
if info[i] == ryan[i] == 0:
continue
elif info[i] >= ryan[i]:
apeach_score += abs(i - 10)
else:
ryan_score += abs(i - 10)
if ryan_score > apeach_score:
if max_value[0] == ryan_score - apeach_score:
if not update_answer(answer[0], ryan):
answer.clear()
answer.append(ryan)
elif max_value[0] < ryan_score - apeach_score:
max_value[0] = ryan_score - apeach_score
answer.clear()
answer.append(ryan)
def dfs(idx, remain, path):
# 백트래킹1
if idx == 10 and remain >= 0:
# 남은 화살 모두 0점에 쏘기
last_arrow = remain
result_path = path[:] + [last_arrow]
calculate_score(result_path)
# 백트래킹2
if idx == 11 or remain < 0:
return
dfs(idx + 1, remain - (info[idx] + 1), path + [info[idx] + 1])
dfs(idx + 1, remain, path + [0])
max_value = [-1]
answer = []
dfs(0, n, [])
if len(answer) == 0:
return [-1]
else:
return answer[0]3. 후기
처음에는 중복조합으로 풀고 공식 해설을 봤는데, 가장 많은 풀이 방식이 DFS를 통한 접근이라고 해서 해설을 읽고 풀어봤다.
카카오 코딩테스트에서는 itertools를 활용하는 풀이가 자주 출제되는 느낌이다. 중복조합 combinations_with_replacement은 자주 사용하지 않았는데 이번 기회를 통해 학습했다.
수정 전: 동점일 경우 answer에 모두 append()한 후 마지막에 한 번 계산
length = len(answer)
for i in range(10, -1, -1):
d = defaultdict()
for j in range(length):
d[j] = answer[j][i]
temp = sorted(d.items(), key=lambda x: -x[1])
if temp[0][1] > temp[1][1]:
return answer[temp[0][0]]
else:
continue수정 후: 아래 코드를 통해 동점끼리 즉시 비교
def update_answer(a, b):
return a[::-1] > b[::-1]바킹독님이 올리신 풀이법을 참조했다. for문을 사용하지 않고 슬라이싱을 통해 비교하는 방식이다.
안녕하세요!