[Python/파이썬] 2022 KAKAO BLIND RECRUITMENT 양궁대회

프로그래머스

코드

from collections import deque

def solution(n, info):
    answer = []
    max_score = 0
    
    # 10~0점까지 라이언 화살 개수 배열, 현재 점수
    q = deque([([0 for _ in range(11)], 10)])   
    
    while q:
        arr, score = q.popleft()
        if sum(arr) == n: # 남은 화살 모두 소진
            # 점수 계산
            apeach, lion = 0, 0
            for i in range(11):
                if info[i] == 0 and arr[i] == 0: # 둘 다 한 발도 못 맞춘 경우
                    continue
                else:   # 점수 나옴
                    if info[i] >= arr[i]:
                        apeach += 10 - i
                    else:
                        lion += 10 - i
            if lion > apeach:  # 라이언이 이김
                if max_score <= (lion - apeach): # 점수차 최대이면 저장
                    max_score = lion - apeach
                    answer = []
                    answer = [i for i in arr]    
        elif sum(arr) > n:  # 화살 넘치게 쏨
            continue
        elif score == 0:    # 남은 화살 다 소진 못 하고 0점까지
            new_arr = [i for i in arr]
            new_arr[10] = n - sum(new_arr)
            q.append((new_arr, 0))
        else:
            # 어피치가 점수 가져감 (라이언이 0개 맞추기)
            new_arr = [i for i in arr]
            q.append((new_arr, score - 1))
            # 라이언이 점수 가져감 (어피치보다 1개 더 맞추기)
            new_arr2 = [i for i in arr]
            new_arr2[10-score] = info[10-score] + 1
            q.append((new_arr2, score - 1))
    if not answer:
        return [-1]
    else:
        return answer

BFS를 이용하여 풀이하였다.

q에 라이언이 점수별로 쏜 화살 개수를 저장할  배열과 현재 배점을 튜플로 넣어준다. 그 후 q가 빌 때까지 아래의 과정을 반복한다.

1. arr의 원소들의 합이 n이라면 라이언이 쏠 수 있는 화살을 모두 소진한 경우이다. 그러니 이 때 라이언과 어피치의 점수를 계산하여 둘의 점수차가 이전까지 계산된 점수차보다 크거나 같다면 answer를 지금의 화살 개수 배열 리스트로 갱신해준다. 왜 클 때가 아니라 크거나 같을 때이냐면 점수차가 같다면 더 낮은 점수를 많이 맞힌 경우를 return하라는 조건이 있기 때문이다. 이 코드에서 보면 더 낮은 점수를 많이 맞춘 경우가 q에 더 늦게 추가되기 때문에 나중에 나오는 경우가 더 낮은 점수를 많이 맞춘 경우이다. 따라서 같은 점수차일지라도 가장 마지막에 나온 배열이 정답이 되도록 하였다.
   그리고 라이언과 어피치의 총점 계산 시 주의할 점은 둘 다 화살을 맞추지 않았을 경우 그 누구도 점수를 가져가지 않는다는 조건이 있다는 점이다.
2. arr의 원소들의 합이 n을 초과한다면 이는 라이언이 화살을 넘치게 쏜 경우이므로 유효하지 않은 리스트이다. continue하여 버리면 된다.
3. score가 0이 되었다면 화살을 다 소진하지 못하고 0점까지 온 경우이다. 이 경우에는 남은 화살을 다 0점에 맞춘 것으로 하고 q에 추가해준다.
4. 위의 3가지 경우에 해당되지 않는다면 그냥 라이언이 화살을 쏘면 된다. 라이언이 어피치보다 n점에 맞춘 화살 개수가 많기만 하면 n점을 가져갈 수 있으므로 화살을 아끼기 위해서는 어피치보다 1개 더 맞추거나 0개 맞추는 경우만 고려하면 된다.