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

코딩테스트 연습 - 양궁대회 | 프로그래머스 (programmers.co.kr)

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

문제요약)

우선 문제를 간략하게 요약한다면 다음과 같다.

1. 과녁판의 점수는 0점부터 10점까지

2. 어피치가 n발을 쏜 후 라이언이 n발을 쏜다.

3. k점에 화살을 더 많이 맞춘 사람이 k점을 가져간다.(맞춘 횟수가 동일할 경우 어피치가 득점)

4. 최종 점수가 같을 경우 어피치가 우승

5. info에는 어피치가 10점부터 0점까지 점수별로 몇발씩 맞췄는지 정보가 들어있음

6. 라이언이 가장 큰 점수 차이로 우승해야 하는데 가장 큰 점수 차이인 경우가 여러개 존재한다면 가장 낮은 점수를 많이 맞췄을 경우로 리턴

 

문제풀이)

DFS나 백트래킹으로 접근하는 것이 훨씬 효율이 좋지만 어떻게 구현해야 할지 생각이 안나서 중복조합을 사용하는 완전탐색 방식으로 접근했다. 최악의 경우인 10발을 쐈을 때 11개의 점수를 각각 몇발씩 맞추는가에 대한 경우의 수를 구해보면 11H10(184756번)이다.

from itertools import combinations_with_replacement 라이브러리를 이용하면 [9,9,9,9,9,9,9,9,1,1]과 같은 형태로 각 경우들이 튜플로 반환된다. 9점을 8번 1점을 2번 쐈다고 생각하여 구현했다. 

 

**풀이과정중 라이언의 점수가 어치피보다 클 때를 조건으로 거는 실수를 했었는데 구해야 하는 경우가 어피치와의 점수차가 큰 경우이기 때문에 peach - lion으로 비교해야한다!

코드)

from itertools import combinations_with_replacement


def solution(n, info):
    bestPoint = 0 #현재까지 어피치와의 가장 큰 점수차
    bestCount = [] #현재까지 점수차가 가장 클 때에 라이언의 과녁
    winFlag = 0
    for lion_count in combinations_with_replacement([10,9,8,7,6,5,4,3,2,1,0],n):
        lion = 0
        peach = 0
        for index, count in enumerate(info): # count = 어피치가 n점 맞춘횟수(10점,9점,8점,...)
            point = 10 - index # 10,9,8,7,6...
            if count > 0 or lion_count.count(point) > 0:
                if count < lion_count.count(point): # 라이언이 point점 맞춘횟수  
                    lion += point
                else:
                    peach += point
        if lion - peach > 0:
            if bestPoint < lion - peach:
                winFlag = 1
                bestPoint = lion - peach
                bestCount = lion_count
                
            elif bestPoint == lion - peach:  
                change = 0 
                for i in range(0,11): # 가장 낮은 점수를 더 많이 맞힌 경우
                    if bestCount.count(i) < lion_count.count(i):
                        #print(i,bestCount.count(i),lion_count.count(i))
                        change = 1
                        break
                    elif bestCount.count(i) == lion_count.count(i):
                        continue
                    else:
                        break
                if change == 1: 
                    #print("lion_count: ",lion_count)
                    #print("bestCount:  ",bestCount)
                    bestCount = lion_count
                    bestPoint = lion - peach
                

    if winFlag == 1: # 점수별로 맞춘 횟수를 리스트에 재배열
        answer = []
        for i in range(10,-1,-1):
            answer.append(bestCount.count(i))
        return answer
    else:
        return [-1]