🐒 문제
https://programmers.co.kr/learn/courses/30/lessons/92342
✍ 나의 풀이
from itertools import combinations
def solution(n, info):
apeach = 0
trials = []
info = info[::-1]
for i in range(11):
if info[i]:
apeach += i
# 라이언이 게임을 시작하기전 어피치가 득점한 점수를 저장한다.
for r in range(1,n+1): # 조합에서 r개를 뽑는다
# 라이언에게 화살이 n개 주어진다. 화살 r개를 사용해서 1점부터 10점까지의 과녁판에 명중하여 점수를 얻을 경우의 수를 뽑는다.
for c in combinations([i for i in range(1,11)],r):
tmp_apeach = apeach # 밀어내기 방식으로 라이언이 점수를 얻음에 따라 어피치의 점수가 변하므로 임시로 저장한다.
for i in c: # 라이언이 i점수 과녁에서 득점했을때
if info[i]: # 어피치가 이미 득점했던 과녁이면
tmp_apeach -= i # 라이언이 얻은만큼 어피치는 점수를 잃는다.
if sum(c) > tmp_apeach: # 라이언의 점수가 어피치보다 큰 경우를 trials에 저장한다.
trials.append([c, sum(c)-tmp_apeach])
# 문제에서는 가장 큰 점수차이로 이기는 경우를 출력해야하므로 다른 경우와 비교를 위해 점수차이도 함께 저장한다.
candidate = []
diff_max = -1 # 최고 점수차이
leftarrow = -1 # 남은 화살 수
for trial,diff in trials:
rion = n # 라이언이 가진 화살 수를 임시변수 rion에 저장한다.
for i in trial[::-1]: # 인덱스랑 과녁판 점수를 맞춰주기 위해 뒤집는다
rion -= info[i] + 1 # 어피치가 맞힌 화살보다 라이언이 화살을 1개 더 맞혀야 i점 과녁판에서 득점한다.
# 어피치가 맞힌 화살 갯수 + 1개를 사용했으므로 라이언이 사용한 화살 갯수에서 뺀다.
if rion < 0: # 라이언이 가진 화살 갯수를 넘으면 그 경우의 수는 패배이므로 후보에서 탈락시킨다.
break
else:
if diff >= diff_max: # 승리한 경우의 수에서 최대 점수차이의 경우의 수가 등장하면
diff_max = diff # 최대 점수차이를 갱신
candidate = trial # 후보 경우의 수 갱신
leftarrow = rion # 승리하고 남은 화살의 수를 저장/갱신
if not candidate: # 만약 후보가 없으면 (승리하는 경우의 수가 존재하지 않으면)
return [-1] # 문제에 명시된 대로 [-1] 리턴
answer = [0]*11 # 출력용 배열 (라이언이 i점수 과녁판에 몇개의 화살을 맞히는지)
for i in candidate: # 최대 점수차이로 승리하는 경우의 수에서 라이언이 명중시키는 i점 과녁판을 확인
answer[i] += (info[i]+1) # 어피치보다 화살을 1개 더 맞힌다.
answer[0] = leftarrow # 남은 화살 0점에 전부 쏴버린다.
return answer[::-1] # 배열 뒤집어서 출력하기
문제이해가 어려워서 다른거 하면서 풀이 방법을 구상했다.
라이언이 이길 모든 경우의 수를 찾아야 한다는 생각에 combinations를 떠올렸다.
다른 풀이 확인하다가 itertools 의 combinations_with_replacement 를 사용한 풀이들이 있는 것 같더라.
combinations 와 다르게 요소가 중복되는 조합을 뽑아낸다.
얘도 나중에 엄청 유용하게 쓰일 것 같다.
처음 코드 (오답)
from itertools import combinations
def solution(n, info):
apeach = 0
trials = []
candidates = []
info = info[::-1]
for i in range(11):
if info[i]:
apeach += i
for r in range(1,n+1):
for c in combinations([i for i in range(1,11)],r):
#print(u)
#겹치는것만 빼야대
tmp_apeach = apeach
for i in c:
if info[i]:
tmp_apeach -= i
if sum(c) > tmp_apeach:
trials.append(c)
for trial in trials:
rion = n
#print(trial)
for i in trial[::-1]:
rion -= info[i] + 1
if rion < 0:
break
else:
candidates.append(trial)
if not candidates:
return [-1]
answer = [0]*11
for i in candidates[-1]:
answer[i] += (info[i]+1)
return answer[::-1]문제조건 중
라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.가장 큰 점수 차이가 아닌, 최고 득점을 기준으로 삼은 부분과
가장 낮은 점수를 더 많이 맞힌 경우 (남은 화살 0점에 쏘기)
를 고려하여 다시 코드를 짯다.
sort 같은거 써서 코드를 좀 더 간결히 만들 수 있을거 같은데..
리팩토링
from itertools import combinations
def solution(n, info):
apeach = 0
trials = []
info = info[::-1]
for i in range(11):
if info[i]:
apeach += i
for r in range(1,n+1):
for c in combinations(range(1,11),r):
tmp_apeach = apeach
for i in c:
if info[i]:
tmp_apeach -= i
if sum(c) > tmp_apeach:
trials.append([c,sum(c)-tmp_apeach])
trials.sort(key= lambda x:(x[1],-x[0][0]), reverse=True)
# 라이언이 어피치에게서 큰 점수차이로 승리하는 경우를 우선순위로, 낮은 점수의 과녁판을 많이 맞힌 경우를 다음 우선순위로 하여 오름차순으로 정렬
for trial,diff in trials:
rion = n
for i in trial[::-1]:
rion -= info[i] + 1
if rion < 0: # 라이언이 화살이 부족해서 패배하는 경우는 넘어감
break
else: # 라이언이 승리하는 경우에서 가장 점수차이가 크고, 낮은 점수의 과녁판을 많이 맞힌 경우을 발견
answer = [0]*11
for i in trial:
answer[i] += (info[i]+1)
answer[0] = rion # 남는 화살 0점에 다 쏴버리기
return answer[::-1] # 문제 조건에 맞게 뒤집어서 리턴
# 라이언이 승리할 수 없는 게임이면
return [-1]
sort 를 사용하고, 간결하게 코드를 작성해보았다.
쥐구멍에 볕드는 날