[프로그래머스] 92342번_양궁대회 (파이썬/Python)

92342번_양궁대회
https://programmers.co.kr/learn/courses/30/lessons/92342

문제 요약
1. 양궁대회에서 라이언이 어피치를 이기는 경우를 구해서 과녁 위치에 따라 몇 발을 맞추면 되는지 리스트로 출력해야한다.
2. 어피치가 모든 화살을 쏜 다음, 라이언이 어피치와 같은 개수의 화살을 쏜다.
3. 과녁 위치마다 과녁 점수가 다르고, 라이언이 어피치를 이기는 경우 중 점수 차이가 가장 큰 경우를 출력한다.
4. 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러가지일 경우, 가장 낮은 점수를 더 맞힌 경우를 출력한다.

4번 조건 같은 경우,
[2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야한다.

라이언이 효율적으로 화살을 사용하기 위해서는 어피치가 이미 맞춘 점수는 아예 0발을 맞춰서 버리거나, 어피치보다 1발 더 맞춰서 그 점수를 가져올 수 있다.
어피치가 10점 과녁을 1발 맞췄을 경우, 라이언은 0발 맞추거나 2발 맞추는 경우 두 가지만 생각할 수 있다!

import copy
answer = []
maxV = 1

def cal(L, A):
    apeach, lion = 0, 0
    for idx in range(11):
        if A[idx] == 0 and L[idx] == 0:
            continue
        elif A[idx] < L[idx]:
            lion += (10 - idx)
        else:
            apeach += (10 - idx)
    return lion - apeach

def compare(res, L):
    global answer, maxV

    if maxV < res:
        answer = [copy.deepcopy(L)]
        maxV = res
    elif maxV == res:
        answer.append(copy.deepcopy(L))

# solution 1
def solution(n, info):
    global answer

    def score(s, L, cnt):

        if cnt == 11:
            if sum(L) == n:
                compare(cal(L, info), L)

            elif sum(L) < n:
                L[10] += n - sum(L)
                compare(cal(L, info), L)
                L[10] -= n - sum(L)
            return
        for i in range(s, 11):
            L[i] = info[i] + 1
            score(i + 1, L, cnt+1)
            L[i] = 0
            score(i + 1, L, cnt+1)

    score(0, [0] * 11, 0)

    if not answer:
        return [-1]
    answer.sort(key=lambda x: x[::-1])
    return answer[-1]

1. 어피치와 라이언 모두 과녁을 맞히지 못 한 경우에는 아무도 점수가 추가되지 않는다!! -> 점수 계산할 때 조건이 세 개 필요
2. 점수 차이를 계산해서 최댓값일 경우엔 해당 경우가 정답
3. 점수 차이가 최댓값인 경우가 여러 개일 경우 리스트에 해당 경우를 추가 -> 마지막에 lambda로 정렬해서 낮은 점수가 제일 높은 경우만 출력
4. 리스트를 추가할 때 얕은 복사되므로 deepcopy 사용해줬다
5. 어피치보다 한 발 더 맞췄을 때랑, 0발 일 때 두 가지 경우에 재귀를 돌려서 모든 경우를 구해줬다.
6. 끝까지 다 돌았는데 아직도 화살이 남은 경우에는 0점 과녁에 남은 화살을 추가해줬다. (가장 낮은 점수를 더 맞힌 경우를 출력해야하므로)

# solution 2
def solution(n, info):
    global answer

    def score(s, L, cnt):

        if not cnt:
            compare(cal(L, info), L)
            return
        if s == 10 and cnt:
            L[10] = cnt
            score(s+1, L, 0)
            L[10] = 0
        else:
            if info[s]+1 <= cnt:
                temp = info[s] + 1
                L[s] = temp
                score(s+1, L, cnt - temp)
                L[s] = 0
            score(s+1, L, cnt)


    score(0, [0] * 11, n)

두 번째 방법은 점수를 매길 때 for문을 사용하지 않고, 함수에 인덱스(과녁 위치)를 같이 넘겨줘서 해당 인덱스에 바로 화살을 매겨줬다. 모든 경우를 확인하는 1번보다 2번이 훨씬 짧게 걸렸다.
1. cnt는 남은 화살의 개수
2. 라이언이 남은 화살이 어피치가 맞춘 화살+1 보다 클 경우, 해당 과녁에 화살 추가/ 적을 경우 라이언은 해당 과녁 0발

---

풀이 방법이 잘못된 줄 알고, 다른 풀이 방법으로 두 번 풀었다.
알고보니까 cal 함수에서 for문 범위를 잘못 설정해준 거였다...
뭔가 잘못됐을 때는 전체적으로 확인할 필요가 있다.