[프로그래머스] 양궁 대회 (2022 KAKAO BLIND) / python

1. 문제

프로그래머스

 

2. 풀이 전 계획과 생각

입력의 형식을 파악 후 어떤 식으로 저장할지 생각

• N → 화살의 개수
• info → 어피치가 맞힌 과녁 점수의 개수를 순서대로 담은 배열 (10점부터 0점까지)

 

구하고자 하는 바

이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 
n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를
10점부터 0점까지 순서대로 정수 배열 리턴
만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 리턴

 

행위의 규칙성, 패턴 파악

완전탐색으로 먼저 접근해보자. N발 마다 라이언이 어디 점수에 꽂힐지에 대한 시간복잡도는 O(11 ^ 10)이다.

 

3. 풀이하면서 막혔던 점과 고민

🤔 모든 경우를 탐색하되 시간복잡도가 너무크다. 어떻게 가지치기를 해줄 수 있을까?

K개 중 하나를 N번 선택하는 방법 대신 중복 조합으로 풀자.
11H10이므로 20C10 = 184756이므로 가능하다.
그리고 그때마다 점수를 계산한다.
전체 시간 복잡도는 184756 * 11 + 184756 log 184756 < 17 * 184756 = 3140852 이다.

 

4. 1차 풀이 - 중복 조합

from itertools import combinations_with_replacement
LENGTH = 11

def solution(n, info):
    lion_scores = []
    for element in combinations_with_replacement(range(LENGTH), n):
        peach_score = 0
        lion_score = 0
        lion_info = [0] * LENGTH
        for idx in element:
            lion_info[10 - idx] += 1

        for i in range(LENGTH):
            if info[i] == 0 and lion_info[i] == 0:
                continue
            elif info[i] >= lion_info[i]:
                peach_score += (10 - i)
            else:
                lion_score += (10 - i)

        diff = lion_score - peach_score
        if diff > 0:
            lion_scores.append((diff, lion_info))

    lion_scores.sort(key = lambda x : (-x[0], x[1]))

    if len(lion_scores) == 0:
        return [-1]
    else:
        return lion_scores[0][1]

문제점

정확성 8, 18번 통과하지 못했다.

⇒ 정렬을 잘못해주었다. 정렬할 때, [높은점수의 갯수 ~ 낮은점수의 갯수] 오름차순이 아니라,

[낮은 점수의 갯수 ~ 높은 점수의 갯수] 내림차순이어야 한다.

 

5. 2차 풀이 - 중복 조합

from itertools import combinations_with_replacement

LENGTH = 11

def solution(n, info):
    lion_scores = []
    for element in combinations_with_replacement(range(LENGTH), n):
        peach_score = 0
        lion_score = 0
        lion_info = [0] * LENGTH
        for idx in element:
            lion_info[10 - idx] += 1

        for i in range(LENGTH):
            if info[i] == 0 and lion_info[i] == 0:
                continue
            elif info[i] >= lion_info[i]:
                peach_score += (10 - i)
            else:
                lion_score += (10 - i)

        diff = lion_score - peach_score
        if diff > 0:
            lion_scores.append((diff, lion_info[::-1]))

    lion_scores.sort(key=lambda x: (x[0], x[1]), reverse=True)

    if len(lion_scores) == 0:
        return [-1]
    else:
        return lion_scores[0][1][::-1]

 

6. 다른 풀이 - 백트레킹

각 점수를 아예 안 맞추거나 어피치보다 1발을 더 맞히는 경우로
각 점수(10점 ~ 0점)마다 2가지(총 2048가지)를 완전 탐색하면 된다.
이렇게 가능한 모든 경우를 살펴보면서 라이언과 어피치의 최대 점수 차이를 구하면 된다.

 

어피치가 [2,0,1,1,0,0,0,0,0,0,0]처럼 화살을 맞췄을 경우 라이언은 과녁 점수 10점을 3발 맞추거나 0발 맞추거나만 선택하면 된다.
9점~0점도 동일한 방식으로 어피치보다 1발을 더 맞추거나 아예 안 맞추도록 구현하면 되고,
중간에 화살을 다 쐈을 경우는 나머지 과녁 점수를 모두 0발 맞춘 것으로 처리하면 된다.

만약 1점까지 쏘고도 화살이 남았을 경우는 남은 화살을 0점에 다 쏘도록 처리할 수 있다.

이렇게 가능한 모든 경우를 살펴보면서 라이언과 어피치의 최대 점수 차이를 구하면된다.

 

⇒ 각 10점 ~ 1점마다

• 점수를 아예 안 맞추는 경우
• 어피치보다 1발을 더 맞히는 경우
• 단, 중간에 화살을 다 쐈을 경우 → 나머지 과녁 점수를 모두 0발 맞춘 것으로 처리
• 만약, 1점까지 쏘고도 화살이 남았을 경우 → 남은 화살 0점에 다 쏘도록 처리

 

⇒ go(어피치 점수, 라이언 점수, 남은 발, idx)

max_diff = 0
answer = []

def go(info, shoot, n, i):
    global answer, max_diff

    if i == 11:
        if n != 0:
            shoot[10] = n

        score_diff = calculate_diff(info, shoot)

        if score_diff <= 0:
            return

        result = shoot[::]
        if score_diff > max_diff:
            max_diff = score_diff
            answer = [result]
            return

        if score_diff == max_diff:
            answer.append(result)
        return

    # 점수 먹는 경우
    if info[i] < n:
        shoot.append(info[i] + 1)
        go(info, shoot, n - info[i] - 1, i + 1)
        shoot.pop()

    # 점수 안 먹는 경우
    shoot.append(0)
    go(info, shoot, n, i + 1)
    shoot.pop()

def calculate_diff(info, shoot):
    peach_score, ryan_score = 0, 0
    for i in range(11):
        if (info[i], shoot[i]) == (0, 0):
            continue
        if info[i] >= shoot[i]:
            peach_score += (10 - i)
        else:
            ryan_score += (10 - i)

    return ryan_score - peach_score

def solution(n, info):
    global answer, max_diff
    go(info, [], n, 0)

    if len(answer) == 0:
        return [-1]

    answer.sort(key=lambda x: x[::-1], reverse=True)
    return answer[0]

 

7. 풀이 후 알게된 개념과 소감

• 모든 경우를 따질 때, 시간복잡도를 낮추기 위해서는 가지치기할 것이 무엇이 있는지 확인할 수도 있지만,
  애초에 탐색할 때 필요한 부분만 탐색하는 방법도 있다.
• 중복으로 뽑을 때, K개 중에 N번 선택하는 것 뿐만 아니라, 중복 조합으로 접근할 수도 있다.