문제
2022 KAKAO BLIND RECRUITMENT - 양궁대회
https://school.programmers.co.kr/learn/courses/30/lessons/92342
나의 해결법(성공)
from itertools import combinations_with_replacement
def solution(n, info):
answer = []
# 점수차이, 해당 배열 => -1 로 초기화할 경우 비긴 경우도 라이언승으로 함
# 그래서 0으로 해야함.
small = [0,[0,0,0,0,0,0,0,0,0,0,0]]
for cwr in combinations_with_replacement([0,1,2,3,4,5,6,7,8,9,10], n):
# 전체 중복 조합을 구한다.
dic = dict()
a_score = 0
r_score = 0
for c in cwr:
# dict 에 정렬한다.
if c not in dic:
dic[c] = 1
else:
dic[c] += 1
# dict의 list화
r = []
for i in range(10,-1,-1):
r.append(dic.get(i,0))
# 점수 비교
for i in range(11):
a_score, r_score = get_score(10-i,info[i],r[i],a_score,r_score)
diff = r_score-a_score
# 그냥 값이 크면
if diff > small[0]:
small = [diff,r]
# 같을 경우
elif diff == small[0]:
for i in range(10,0,1):
tmp = r[i] - small[1][i]
if tmp > 0 :
small = [diff, r]
break
if small[0] == 0:
return [-1]
else:
return small[1]
return answer
# 점수를 구하는 함수
def get_score(point,a,r,a_score,r_score):
if point == 0 or(a == 0 and r == 0):
return [a_score,r_score]
if a >= r :
a_score += point
else:
r_score += point
return [a_score, r_score]
# 문제 정리
# a = b = 0 이면 아무도 점수 x
# a = b 인경우 어피치가 우선 이김
# 10~0까지
# 최종점수가 같으면 어피치가 우승자
# 같은 화살을 쏠꺼임
# n은 쏜 화살
# info 는 어피치 랭크문제 풀이(중복 조합 사용)
일단 문제의 어휘가 조금 애매한 부분이 많았던 문제였다.
- 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.(0점을 맞추는건 점수가 없지만 적중한 것에는 포함된다.)
해당 문제를 보고 처음에는 어떻게 접근을 할까 고민하다가 주어진 n의 값이 작은점(최대 10), 또한 info의 길이가 작은점(최대 11)을 이용하여 그리디로 접근을 하였다.
중복 조합을 사용하여 0~10까지의 수를 랜덤으로 화살수 만큼 조합하고 갯수를 세준 뒤 문제 조건처럼 진행해주었다.
차이의 값이 클 경우는 바로 갱신을 해주되 만약 같았을 경우에는 낮은 점수부터 두개를 빼주어서 만약 빼준것중에 0 이 아닌 양수를 만났을 경우 라이언이 큰 경우가 된다.
그래서 해당 값을 갱신해주고 만약 갱신이 이루어지지 않았을 경우 -1 출력
하지만 해당 풀이는 끝나고 알고리즘의 코드 리뷰를 하면서 아쉬운 점이 많았다.
일단 [0,0,0...0] 부터 필요 없는 이길수 없어도 모든 중복 조합을 구하니 통과는 했지만 다른 동기의 코드에 비해 느렸다.
한마디로 너무 많은 의미없는 조합까지 확인하고 검사하느라 시간이 오래걸렸던 것이다.
알고리즘 스터디 - 동기의 풀이
from itertools import combinations
def chk(arr):
global max_diff
li_info = [0] * len(ap_info)
arr_cnt = 0
score = 0
for i in arr:
req_arrow = ap_info[i] + 1
if req_arrow <= arrow_num:
arr_cnt += req_arrow
li_info[i] = req_arrow
if arr_cnt > arrow_num:
return -1
ap_score = 0
li_score = 0
for i in range(info_len):
if li_info[i] > ap_info[i]:
li_score += 10-i
else:
if ap_info[i] != 0:
ap_score += 10-i
if li_score > ap_score:
score_diff = li_score - ap_score
if score_diff >= max_diff:
max_diff = score_diff
if arr_cnt < arrow_num:
li_info[-1] += arrow_num-arr_cnt
return li_info
else:
return -1
else:
return -1
def solution(n, info):
global ap_info, arrow_num,info_len, max_diff, max_idx
max_diff = 0
arrow_num = n
ap_info = info
info_len = len(info)
ans = []
for arrow_cnt in range(1,n+1):
combi = list(combinations([i for i in range(len(info))], arrow_cnt))
print(combi)
for c in combi:
res = chk(c)
if(res != -1):
ans = res
if ans == []:
return [-1]
else:
return ans동기의 풀이(조합 사용)
해당 풀이의 로직은 문제에서 가장 작은 점수를 맞춘 화살 기준으로 순서가 매겨지며 같은 점수에 많이 맞춰도 1회만 점수가 들어온다는 점을 사용했다
for문을 조합 위에서 돌렸으며 어피치를 이길 수 있는 경우만 계산을 했다.
처음에 이 생각을 했다가 남은 화살을 처리를 못했다.
하지만 문제를 다시 오래 읽어보니 남은 화살은 0점에 다 쏴버리는게 점수는 얻지못하지만 높은 등수를 노릴 수 있어서 for 문에서 적중한 갯수를 굳이 10개를 채울 필요가 없었다.
남은 화살은 다 0점에 모아 놓으면 되었다!
실제로 끝나고 두 코드를 비교해서 돌려보니 둘다 정답이지만 시간 효율성이 30배이상 차이가 났다.
해당 이길수있는 조합 그리고 0을 포함해서 진짜 모든 경우의 수를 비교한 부분에서 차이가 났다.
결론
문제 이해도가 나보다 빠르고 높아서 더 좋은 코드를 생각해낸것 같다.(문해력 너무 어려워,,,,)
그래도 스터디를 꾸준하게 진행하고 서로의 코드를 보면서 새로운 알고리즘 생각을 볼 수 있는 부분에서 꾸준하게 이어가면 좋은 습관 같다!
