프로그래머스

[프로그래머스] 양궁대회

진철 2024. 5. 3. 15:37
728x90
반응형

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92342#

문제 풀이 방법

데이터의 종류가 많지 않으므로 활을 쏠 수 있는 모든 경우의 수 찾는 완전 탐색 방법을 사용한다.
모든 경우의 수를 하나씩 탐색하면서 차이값이 현재 차이값보다 크다면 해당 경우 차이값으로 업데이트하고 이 경우를 후보에 넣어준다.
단, 모든 탐색 이후에도 차이값이 0이라면 이는 라이언과 무지가 모든 점수에서 비긴 경우이므로 라이언이 절대 이길 수 없는 경우이다. 따라서, 이때만 -1을 예외적으로 반환한다.
후보가 여러 가지일 경우에 낮은 득점을 많이 한 것을 골라야 하므로 0점부터 10점까지 오름차순으로 맞춘 갯수가 0개가 아닌 점수를 반환한다.
해당 점수를 기준으로 후보들을 내림차순하여 가장 앞의 값을 정답으로 도출한다.

풀이 코드
def distribution(arrows, score, arrow_per_person=None, idx=0):
    if arrow_per_person is None:
        arrow_per_person = [0] * score

    if arrows == 0:
        return [tuple(arrow_per_person)]

    distributions = []

    for i in range(idx, score):
        if arrows > 0:
            arrow_per_person[i] += 1
            next_distributions = distribution(arrows - 1, score, arrow_per_person, i)
            distributions.extend(next_distributions)
            arrow_per_person[i] -= 1

    return distributions    

def solution(n, info):
    answer = []
    maxv = 0
    real = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    all_distributions = distribution(n, 11)
    
    for temp in all_distributions:
        ryan = 0
        muzi = 0
        for i in range(len(temp)):
            if temp[i] or info[i]:
                if temp[i] > info[i]:
                    ryan += real[i]
                else:
                    muzi += real[i]
        
        gap = ryan - muzi
        
        if gap > maxv:
            answer = []
            answer.append(temp)
            maxv = gap
        elif gap < maxv:
            continue
        else:
            answer.append(temp)
    
    if not answer:
        return [-1]
    elif maxv == 0:
        return [-1]
    
    idx = -1
    for i in range(len(answer[0])-1, -1, -1):
        maxv = -float('inf')
        for a in answer:
            if a[i] == 0:
                continue
            if maxv < a[i]:
                maxv = a[i]
        if maxv > 0:
            idx = i
            break
    
    answer.sort(key = lambda x:-x[idx]) 

    return answer[0]

 

느낀점

수의 크기가 작지 않아서 완전 탐색으로 해결하는 것이 오히려 더 나은 문제였다.

다른 분들의 풀이를 보니, itertools나 Counter를 통해서 완전 탐색을 하셨던데, 왜 그 방법을 생각하지 못했는지 좀 아쉽다 ... (실제로도, 재귀 함수를 만드는 데 시간을 제일 많이 사용하였다.)

그리고 처음에는 8, 18, 23번 테스트 케이스가 오답이 났었다.

8, 18번의 경우에는 낮은 점수를 많이 맞춘 경우를 도출하기 위해서 오름차순으로 정렬을 했기 때문이었다.

바보 같이 반례를 생각하지 못하고 코드를 작성한 것이 원인이었다.

또한 23번의 경우에는 라이언과 무지가 모두 비기는 경우를 생각하지 못했기 때문이었는데, 이는 다른 분의 도움이 없었다면 엄청 많이 헤맸을 듯하다.

항상 코딩 테스트 연습을 할 때마다 느끼는 거지만, 모두 오답이 나는 것보다 한 두 문제에서 오답이 날 때 가장 막막한 것 같다. (정말 정말 화가 나지 않을 수 없다 !!)

그럴 때는 항상 반례가 뭔지 곰곰히 생각해보고 ! 코드 작성하는 단계를 다시 생각해봐야할 것을 명심하자 !

728x90
반응형