[Coding Test] 양궁대회

프로그래머스
2022 KAKAO BLIND RECRUITMENT
양궁대회

1. 문제

2. 생각의 흐름

1. 처음에는 중복 조합을 이용하여 n발을 쏠 때 나올 수 있는 모든 경우의 수를 구해 가장 큰 점수차인 경우를 구하려고했다.
2. 모든 경우의 수를 담고 있는 list를 탐색하며 가장 큰 점수차가 나올 경우 점수 차와 answer을 갱신하여 정답을 도출하려했다.
3. 위의 방법대로 테스트를 통과하여 정답을 제출 하였지만 8번,18번 테스트를 통과하지 못해 낮은 점수대를 많이 쏘는 경우를 리턴하는 조건을 붙였지만 계속 통과하지못함..
4. 다시 처음으로 돌아가 모든 경우의 수가 아닌 다른 방법을 모색
5. 라이언이 점수를 얻기 위해서는 어피치 보다 1발 이상 더 쏴야한다.
   5.1 어피치 보다 1발 더 많이 쏘는 경우와 그렇지 않을 경우는 0발, 마지막에 화살이 남아있으 면 0점에 모두 소비하는 로직으로 구성.
   5.2 10점 부터 1발 더 쏘거나 0발 쏘는 모든 경우의 수를 list에 담는다.
   5.3 경우의 수가 담긴 list를 탐색하며 점수차와 점수판을 갱신한다.
   5.4 점수차가 같을 경우에는 점수판을 비교하여 낮은 점수대가 많은 쪽으로 갱신한다.
   5.5 answer가 한번도 갱신되지 않을 경우 [-1]을 리턴한다.

3. 나의 풀이

import itertools
from itertools import combinations_with_replacement
import copy
def combination_iter(r_list,n):
    com_list=list(combinations_with_replacement(r_list,r=n))
    return com_list

def calScore(arr2,arr3):
    score1=range(11)
    score1=score1[::-1]
    a_score=0
    b_score=0
    diff1=0
    for i in range(len(arr2)):
        if arr2[i]>arr3[i]:
            a_score+=score1[i]
        elif arr2[i]<=arr3[i] and arr3[i]>0:
            b_score+=score1[i]
    if a_score-b_score>0:
        diff1=a_score-b_score
        return diff1
    else:
        return diff1
def compArr(arr,arr1):
    #print("compare : "+str(arr)+" , "+str(arr1))
    for i in range(len(arr)-1,-1,-1):
        if arr[i]>arr1[i]:
            #print("change : "+str(arr)+" , "+str(arr1)+" "+str(i))
            return arr
        elif arr[i]<arr1[i]:
            return arr1
        elif arr[i]==arr1[i]:
            continue
    #print("last : "+str(arr)+" , "+str(arr1))
    return arr1

def solution(n, info):
    answer = []
    max1=0
    arr=[]
    for idx in range(len(info)):
        if len(arr) == 0:
            if info[idx]<n:
                tmp=[]
                tmp.append(info[idx]+1)
                arr.append(tmp)
                arr.append([0])
            else:
                arr.append([0])
        elif idx==len(info)-1:
            arr_copy=copy.deepcopy(arr)
            arr_tmp=[]
            for c in arr_copy:
                sum_list=sum(c)
                left=n-sum_list
                c.append(left)
                arr_tmp.append(c)
            arr=arr_tmp
        else:
            arr_copy=copy.deepcopy(arr)
            arr_tmp=[]
            for c in arr_copy:
                sum_list=sum(c)
                left=n-sum_list
                if left > 0 and info[idx] < left:
                    c_copy=copy.deepcopy(c)
                    c_copy.append(info[idx]+1)
                    arr_tmp.append(c_copy)
                    c.append(0)
                    arr_tmp.append(c)
                else:
                    c.append(0)
                    arr_tmp.append(c)
            arr=arr_tmp
    
    for score_tb in arr:
        diff = calScore(score_tb,info)
        if max1 < diff:
            max1=diff
            answer=score_tb
        elif max1==diff and diff!=0:
            #print(answer)
            answer=compArr(answer,score_tb)
            #print(answer)

    return answer if len(answer) > 0 else [-1]

4. 느낀점

조합, 순열, 중복조합, 중복순열
dfs,bfs
자주 나오는 알고리즘에 대해 확실히 알아두자.