[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 양궁대회

https://programmers.co.kr/learn/courses/30/lessons/92342

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

2022 카카오 블라인드 채용 문제다.

[문제 설명]

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

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 해주세요.

 

[제한 조건]

• 1 ≤ n ≤ 10
• info의 길이 = 11
  • 0 ≤ info의 원소 ≤ n
  • info의 원소 총합 = n
  • info의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
• 라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11입니다.
  • 0 ≤ return할 정수 배열의 원소 ≤ n
  • return할 정수 배열의 원소 총합 = n (꼭 n발을 다 쏴야 합니다.)
  • return할 정수 배열의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
  • 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
    • 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
    • 예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다.
    • 다른 예로, [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.
• 라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1입니다.
  • 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.

[아이디어]

1) 아무 생각이 안나다가,, 완전탐색은 필요한 것 같고 자연수 분할을 이용할 수 있겠다는 생각이 들었다.

2) n을 1~n개로 분할하는 모든 방법에 대해, 각 분할에 사용된 자연수들을 10점 ~ 0점의 과녁에 쏜 화살 수에 적절히 배치하고, 점수 차를 계산해 점수 차가 커지는 경우에만 ryan을 업데이트한다.

3) 점수 차가 같은 경우에는 문제 조건처럼 뒷쪽 과녁을 더 많이 맞춘 경우에만 ryan을 업데이트한다. 이때 점수 차가 0인 경우에는 어피치가 승리하므로 업데이트 하지 않도록 주의해야한다.

 

from collections import deque
from itertools import combinations_with_replacement as H
from itertools import permutations as P
from itertools import combinations as C

def calc_diff(ryan, info):
    diff = 0
    for i in range(11):
        if ryan[i]+info[i]:
            if ryan[i] > info[i]:
                diff += 10-i
            else:
                diff -= 10-i
    return diff

def check(ryan, info):
    ryan_ = ryan.copy()
    info_ = info.copy()
    while ryan_:
        r,i = ryan_.pop(), info_.pop()
        if i>r: return False
        elif i==r: continue
        elif r>i: return True

def DIVID(n,m):
    if m==1: return [[n]]
    A=[list(x) for x in H(range(1,n),m) if sum(x)==n]
    return A
        
def solution(n, info):
    diff = 0
    ans = [-1]
    for i in range(1,n+1):
        tmp = DIVID(n,i)
        for t in tmp:
            for tt in set(P(t,i)):
                for x in C(range(11),i):
                    ryan = [0]*11
                    for j, k in zip(tt,x):
                        ryan[k] = j
                    c = calc_diff(ryan, info)
                    if diff < c:
                        ans = ryan.copy()
                        diff = c
                    elif diff == c and diff!=0:
                        if check(ryan, ans):
                            ans = ryan.copy()
    return ans

만들어놓고도 5중 for문이라 이게 되나 싶었는데 통과됐다.(시간 여유가 10초로 넉넉해서인듯, 비효율적인 코드임) dfs로 풀었다는 사람들 있던데 봐도 무슨 소린지 모르겠다,,, 비트마스킹을 이용한 풀이가 가장 직관적이고 출제 의도에 가까워보이는 것 같다. 결국 특정 과녁에 대해 이겼느냐 졌느냐만 따지면 되고, 이긴 경우라면 이길 수 있는 최소한의 숫자만 그 과녁에 쓰고 남는 화살은 맨 마지막 0점에 투자하면 된다. 이겨야하는 과녁들에 사용되는 화살의 수가 n을 넘어가는 경우에는 제외하는 아이디어로 문제 조건을 모두 충족시키면서도, 최소한의 탐색 안에 해결이 가능하다.

# 비트마스킹 활용
def calc_diff(ryan, info):
    diff = 0
    for i in range(11):
        if ryan[i]+info[i]:
            if ryan[i] > info[i]:
                diff += 10-i
            else:
                diff -= 10-i
    return diff

def check(ryan, info):
    ryan_ = ryan.copy()
    info_ = info.copy()
    while ryan_:
        r,i = ryan_.pop(), info_.pop()
        if i>r: return False
        elif i==r: continue
        elif r>i: return True
        
def solution(n, info):
    diff = 0
    ans = [-1]
    for subset in range(1,2<<10):
        ryan = [0]*11
        cnt = 0
        for i in range(10):
            if subset & (1<<i):
                ryan[i] = info[i]+1
                cnt += ryan[i]
        if cnt > n: continue
        ryan[-1] = max(n - cnt, 0)
        c = calc_diff(ryan, info)
        if diff < c:
            ans = ryan.copy()
            diff = c
        elif diff == c and diff!=0:
            if check(ryan, ans):
                ans = ryan.copy()
        
    return ans

비트연산자 &를 활용해 10점 ~ 1점 과녁의 승리 여부를 판단하는 것이 인상적이다. 아직 비트 연산이 익숙하지 않아서 연습이 필요할 것 같다.

이게 왜 level2,,?ㅎㅎ