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

문제

문제 설명

카카오배 양궁대회가 열렸습니다.
라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
   1. 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다. 

      

   2. 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
      • 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
      • 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
   3. 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.

화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.

 

입력 & 출력

입출력 예

ninforesult

5	[2,1,1,1,0,0,0,0,0,0,0]	[0,2,2,0,1,0,0,0,0,0,0]
1	[1,0,0,0,0,0,0,0,0,0,0]	[-1]
9	[0,0,1,2,0,1,1,1,1,1,1]	[1,1,2,0,1,2,2,0,0,0,0]
10	[0,0,0,0,0,0,0,0,3,4,3]	[1,1,1,1,1,1,1,1,0,0,2]

 

새로 사용한 함수

combinations_with_replacement(score, n)

기존 많이 사용하였던 combinations 함수와는 다르게 중복을 허용하는 중복 조합 함수입니다. 

첫 번째 인자로는 조합을 할 순서가 있는 값을 넣도록 하며 두 번째 인자에는 첫 번째 인자로 몇 개짜리 값을 구성할지에 대한 상수를 입력하여 사용합니다.

 

이번 문제에서 score당 맞출 수 있는 화살 개수에 적합한 내용으로 생각되어 사용하였습니다.

 

풀이 과정

처음 풀이과정 코드 2와 같으며  화살이 사용되고 점수를 획득하였을 때 자신이 점수를 획득하면서 상대방이 점수를 획득하지 못하는지 여부를 판별하면서 화살 한발 한 발의 밸류 값을 책정하여서 이것을 배열로 저장 이 밸류 값 순서대로 정렬하여 차례차례 필요한 화살 숫자를 이용하여 높은 밸류 위주로 쏜다고 가정하고 예외 처리를 하는 방식으로 구현하였고 제출 전 테스트 케이스도 다 통과를 하였지만 문제가 있었습니다.

 

제출 시 60점대의 점수만을 획득할 수 있었고 어떤 문제인지 문제의 제한 사항을 꼼꼼히 읽어보니 문제점을 알 수 있었습니다.

 

생각 못했던 제한사항은 밑의 내용이며 위에 설명한 경우대로 수행할 경우에는 가장 큰 점수 차이로 승리하는 경우의 수를 고려할 수 있지만 밑의 내용이 누락되어 같은 점수 차이로 이기지만 낮은 점수를 더 많이 맞힌 경우가 고려되지 않기 때문에 문제가 생겼다. 이에 풀이과정을 수정하였습니다. 

• 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

해당 사항을 고려하기 위해서 0점부터 차례대로 낮은 수를 이기는 경우를 상정하고 또다시 밸류 값을 기준으로 하여서 하나씩 채워나가면서 탐색하는 방법으로 구현하였으나 결과적으로 해당 방법으로 구현하는데 실패하였다. 하지만 이렇게 생각한 것조차도 틀린 전제였습니다.

 

마지막 겪었던 문제점으로는 밑과 같은 값이 인풋으로 입력되게 될 때

info = [0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0] #3
print(solution(3, info))

출력 값이 [1,0,2,0,0,0,0,0,0,0,0]가 나와야 하지만  [1,1,0,0,1,0,0,0,0,0,0] 나오는 문제였고 이는 높은 밸류부터 순차적으로 들어갈 때 점수 차이가 최대로 날것이라는 잘못된 전제로 인하여 생긴 문제였습니다. 실제로는 이렇게 선형적인 문제가 아니고 남은 화살의 개수로 한 발의 밸류 값이 높은 것을 취하지 않고 다음으로 밸류 값이 높은 것과 다다음으로 높은 것을 획득하였을 때 등의 경우의 수를 고려하여야 하는데 이렇게 하지 못하였었습니다. 다른 로직이 추가된다면 현상태에서 해결방법을 얻을 수 있을 것이라고 생각하였지만 처음부터 접근 방법을 다르게 하는 것이 더 효율적이라고 생각하여 실제 상황이라고 가정하고 다시 구현 방법을 생각해보았습니다.

 

밑의 내용은 이렇게하여 성공한 구현 방법에 대하여 어떻게 생각하고 구현하였는지를 간략하게 나타냅니다.

1. 실제로 양궁을 한다고 생각하고 과녁에 주어진 숫자의 화살을 쏜다고 가정하고 이를 코드로 나타냅니다.

- 실제 양궁을 해서 화살을 쏘게 된다면 각각의 score에 화살을 쏘는 hit_check라고 생각할 수 있고 기본적으로 조합을 나타내며 같은 점수를 두 번 세 번 쏘는 것도 가능하기 때문에 중복 조합이라고 생각할 수 있습니다.

- 이때 중복 조합의 순서가 있는 iteral 한 첫 번째 인자로는 score의 범위에 대한 배열이 들어가고 두 번째 상수 인자는 쏘는 화살의 개수를 사용하면 되겠습니다.

 

2. 1번과 같이 수행하면 실제로 몇 번째 화살이 몇 점을 쏘았는지에 대한 튜플을 얻을 수 있습니다.

 

3. 이렇게 얻은 튜플은 객체에 담아지게 되고 이것은 연속성을 가지고 있기 때문에 for문을 이용하여 하나씩 순차 탐색이 가능, 이렇게 얻은 튜플을 이용하여 배열 값에 어떤 스코어에 몇 발의 화살이 맞았는지를 temp_answer라는 배열을 만들어서 저장하도록 하며 이것은 이후에 info값에 들어온 배열과 비교하여 점수 차이를 확인하고 이를 순회하면서 최대 점수차가 어느 배열의 경우에 생기는지를 확인할 때 쓰도록 합니다.

 

4. 문제에서 어피치가 같은 점수 과녁에 맞힌 화살 개수보다 라이언이 더 많은 개수를 맞추지 못하면 점수를 얻을 수 없다고 하였는데 여기서 제시받은 내용대로 조건문을 구성하도록 합니다.

- 각각의 배열은 배열의 요소를 순서대로 돌면서 하면 되는데 두 개의 배열을 한꺼번에 확인할 때 인덱스 값을 이용하여 해도 되지만 zip함수를 이용하여 구성하였습니다.

 

5. 이렇게 하여 각각 어피치의 점수와 라이언의 점수를 구하게 되고 이 두 개의 값의 차이를 저장하여 다음 튜플에서 들어왔을 때도 비교할 수 있게 준비합니다.

 

6. 각 플레이어 끼리의 점수 차이가 각각의 튜플이 들어왔을 때 달라지므로 최대로 점수차가 날 때를 저장할 수 있게 만들어 이렇게 최대 점수 차이가 날 때 배열을 저장하여 return함수에 사용합니다.

 

7. 마지막으로 서로의 점수 차이가 0보다 작거나 같을 경우는 라이언이 이기는 경우가 아니기 때문에 예외처리 조건에 따라 [-1]을 리턴하도록 하면 원하는 결과를 얻을 수 있습니다.

 

코드

코드 1

from itertools import combinations_with_replacement


def solution(n, info):
    score = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    hit_check = combinations_with_replacement(score, n)

    max_different = 0
    answer = [0] * 11
    for hit_position in hit_check:
        # print(hit_position)
        temp_answer = [0] * 11
        for i in range(len(hit_position)):
            temp_answer[10 - hit_position[i]] += 1
        # print(temp_answer)

        score_check = 10
        apeach_score = 0
        lion_score = 0
        for apeach, lion in zip(info, temp_answer):
            if apeach >= lion and apeach != 0:
                apeach_score += score_check
            elif lion > apeach and lion != 0:
                lion_score += score_check

            score_check -= 1

        temp_different = lion_score - apeach_score
        if max_different < temp_different:
            max_different = temp_different
            answer = temp_answer
    if max_different <= 0:
        answer =[-1]

    return answer

코드 2 - 특정 경우에 따라서 원하는 결괏값을 얻을 수 없음

def solution(n, info):
    answer = [0] * 11
    value_check = []
    for score_index, need_hit in enumerate(info):
        if need_hit > 0:
            value_check.append([(10 - score_index) * 2 / (need_hit + 1), need_hit + 1, score_index])
        else:
            value_check.append([(10 - score_index) / (need_hit + 1), need_hit + 1, score_index])

    value_check.sort(reverse=True)

    remain_arrow = n
    for priority_check in value_check:
        if priority_check[1] <= remain_arrow:
            remain_arrow -= priority_check[1]
            answer[priority_check[2]] = priority_check[1]
        elif remain_arrow == 0:
            break
    if remain_arrow >= 0:
        answer[-1] = remain_arrow

    score_check = 10
    apeach_score = 0
    lion_score = 0
    for apeach, lion in zip(info, answer):
        if apeach >= lion and apeach != 0:
            apeach_score += score_check
        elif lion > apeach and lion != 0:
            lion_score += score_check

        score_check -= 1

    if lion_score < apeach_score:
        answer = [-1]

    return answer