[kakao / 프로그래머스] 92342번 : 양궁대회

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/92342

 

문제 이해 

어피치의 과녁 정보는 info에 담겨있고, 라이언이 n개의 화살을 쏴서 어피치를 최대 점수 차로 이기는 경우의 과녁 정보를 반환하는 문제다. 

어피치와 비기거나 지게되었을 땐 [-1]을 반환한다.

10 - i 점수에서 이겼을때(맞힌 화살의 수가 상대방보다 더 클 때) 10 - i 점수만 받게 된다. 

이렇게 라이언이 어피치를 이기는 경우 중에 최대 점수 차가 나는 경우, 그 경우가 여러개일 경우 낮은 점수를 가장 많이 쏜 경우를 반환하면 된다. 

 

어려웠던 점 

점수 계산하는 건 이해가 갔지만 라이언이 화살을 쏘는 경우를 어떻게 만들어야할지 몰랐다. 

 

배운 점 

구글링해보니 라이언이 이기려면 어피치의 과녁에 있는 갯수보다 +1을 하거나, 해당 과녁은 0개를 맞추고 다른 곳에서 더 많은 점수를 얻는 경우 두가지가 있다고 한다. 그래서 이걸 bfs로 구현하면 된다는 걸 배웠다. 

 

- 정답 풀이 :

 

풀이는 크게 4가지 경우로 나뉘어서 진행된다.

focus, arrow = arrow의 인덱스(10 - 현재 맞추고 있는 과녁의 번호), 화살의 현재 상태 

1. 라이언이 화살 n 개를 모두 쏜 경우 : 어피치와 라이언의 점수를 비교해서 최대 점수차 정보를 res에 추가해간다.

2. 라이언이 화살 n개 초과를 쏜 경우 : continue한다 

3. 라이언이 화살을 덜 쐈는데, 0점을 가리키고 있는 경우 : 0점 인덱스(10)에 남은 화살을 모두 쏘고 (-1, temp)를 q에 추가한다.

4. 라이언이 화살 n개 미만으로 쏜 경우  : 어피치보다 1점 더 큰 값을 추가하거나 0점으로 처리한 화살 정보를 q에 추가한 뒤 bfs를 이어나간다. 

 

1. 화살을 n개 다 쏜 경우는 

i 인덱스에서 어피치나 라이언의 점수가 있다면 누가 더 많이 맞혔나 비교한 뒤 apeach와 lion의 점수의 차이를 구한다. (gap)

lion이 apeach보다 점수가 더 높다면, 그 차이를 계산한 뒤 maxGap을 비교한다. 이때 3가지 경우에 대해 모두 생각해야한다. 

• maxGap이 gap과 같다면 화살 상태를 그대로 추가하고
• maxGap < gap이라면 기존에 있던 res를 초기화한 뒤 해당 화살 상태를 추가한다.
• maxGap > gap이라면 업데이트할 필요가 없으므로 continue한다 

        if sum(arrow) == n:  # 종료조건 1) 화살 다 쏜 경우
            apeach, lion = 0, 0
            for i in range(11):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        apeach += 10 - i
                    else:
                        lion += 10 - i
            if apeach < lion:  # 라이언이 이기면
                gap = lion - apeach
                if maxGap > gap:
                    continue
                if maxGap < gap:
                    maxGap = gap  # 최대점수차 갱신
                    res.clear()
                res.append(arrow)  # 최대점수차를 내는 화살상황 저장

2. 화살을 n개 초과로 쏜 경우 -> 넘어간다 

        elif sum(arrow) > n:  # 종료조건 2) 화살 더 쏜 경우
            continue

3. focus == 10 인 경우, 즉 화살 n개를 다 쏘지 못한 상태로 0점 과녁으로 온 경우. (focus 값은 10 - focus 과녁을 가리키고 있으므로)

arrow를 복사한 temp를 만들어 0점에 남은 화살을 몰아준 뒤 (-1, temp)를 q에 추가해서 끝낸다. (temp를 복사 안하고 바로 arrow를 사용할 수 있지 않나?)

        elif focus == 10:  # 종료조건 3) 화살 덜 쏜 경우
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1, tmp))

 

4. 화살 쏘는 경우 

- 어피치 점수 + 1을 한 뒤 진행하는 경우

- 해당 과녁에 0점 처리를 한 뒤 진행하는 경우

두 가지 경우로 나눠서 bfs를 진행한다. 

         else:  # 화살 쏘기
            tmp = arrow.copy()
            tmp[focus] = info[focus] + 1 
            q.append((focus + 1, tmp))  # 어피치보다 1발 많이 쏘기
            tmp2 = arrow.copy()
            tmp2[focus] = 0
            q.append((focus + 1, tmp2))  # 0발 쏘기

 

참고한 블로그

from collections import deque

def bfs(n, info):    
    res = []
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    maxGap = 0
    
    while q:
        focus, arrow = q.popleft()
        
        if sum(arrow) == n:  # 종료조건 1) 화살 다 쏜 경우
            apeach, lion = 0, 0
            for i in range(11):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        apeach += 10 - i
                    else:
                        lion += 10 - i
            if apeach < lion:  # 라이언이 이기면
                gap = lion - apeach
                if maxGap > gap:
                    continue
                if maxGap < gap:
                    maxGap = gap  # 최대점수차 갱신
                    res.clear()
                res.append(arrow)  # 최대점수차를 내는 화살상황 저장
        
        elif sum(arrow) > n:  # 종료조건 2) 화살 더 쏜 경우
            continue
        
        elif focus == 10:  # 종료조건 3) 화살 덜 쏜 경우
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1, tmp))
        
        else:  # 화살 쏘기
            tmp = arrow.copy()
            tmp[focus] = info[focus] + 1 
            q.append((focus + 1, tmp))  # 어피치보다 1발 많이 쏘기
            tmp2 = arrow.copy()
            tmp2[focus] = 0
            q.append((focus + 1, tmp2))  # 0발 쏘기
    return res

def solution(n, info):
    winList = bfs(n, info)
    
    if not winList:
        return [-1]
    elif len(winList) == 1:
        return winList[0]
    else:
        return winList[-1]