프로그래머스 - 양궁대회 (2022 KAKAO BLIND RECRUITMENT) / Level 2 / Python

문제 📋

코딩테스트 연습 - 양궁대회

풀이 📝

from itertools import combinations_with_replacement
from collections import defaultdict


def compare(ryan, apeach, win_dict):  # 승패 판단
    ryan_score = 0
    apeach_score = 0

    for i in range(11):  # 점수 계산
        if apeach[i] >= ryan[i]:
            if apeach[i] == 0:
                continue
            apeach_score += 10 - i
        else:
            ryan_score += 10 - i

    if ryan_score > apeach_score:  # 라이언이 이겼으면 win_dict에 {점수 차 : [라이언 결과들]} 형태로 같은 점수 차를 갖는 라이언 결과들을 모음
        win_dict[ryan_score - apeach_score].append(ryan)
    return win_dict


def solution(n, info):
    cases = list(combinations_with_replacement([i for i in range(11)], n))
    cands = []
    win_dict = defaultdict(list)

    for case in cases:  # 중복조합을 이용하여 라이언을 쏠 수 있는 모든 경우의 수를 구함
        ryan = [0] * 11
        for i in case:
            ryan[i] += 1
        cands.append(ryan)

    for cand in cands:
        win_dict = compare(cand, info, win_dict)  # 이긴 것만 win_dict에 기록

    if not win_dict:  # 한번도 이길 수 없다면
        return [-1]

    target = win_dict[max(win_dict.keys())]  # 점수 차가 가장 큰 라이언 결과들
    target.sort(key=lambda x: tuple([-x[i] for i in range(10, -1, -1)]))  # 문제의 조건에 따라 정렬
    return target[0]

문제를 보자마자 완전탐색으로 문제를 해결할 수 있는지 판단하기 위해
문제의 입력 크기를 통해 라이언의 양궁 발사 결과 경우의 수를 생각해봤다.

쏠 수 있는 점수는 0~10 총 11개의 경우가 있고 화살의 갯수만큼 해당 점수를 선택 할 수 있는데 중복 선택이 가능하다.
화살의 갯수가 최대 10개이므로 최대 경우의 수는 중복조합을 활용하여 다음과 같이 구할 수 있다.

11H10 = 11+10-1C10 = (11+10-1)! / 10!(11-1)! = 184,756

하나의 경우에 대해서 11번의 비교 연산을 감안하더라도 약 180만 정도이고
또한 문제에서 제한시간이 10초이기 때문에 완전탐색으로 문제를 접근하기로 했다.

모든 경우에 대해서 라이언이 이긴 결과들을
{ 점수 차 : [ 해당 점수 차로 라이언이 이긴 결과들 ] }
와 같은 형태로 저장해주었고 그것들중 점수 차가 가장 큰 것을 가져와 문제의 조건대로 정렬을 수행해주었다.