[Python] 2022 KAKAO BLIND RECRUITMENT : 양궁대회

송진영·2022년 10월 4일
0

프로그래머스-python

목록 보기
9/22

2022 KAKAO BLIND RECRUITMENT : 양궁대회

문제풀이

우선, 이 문제는 bfs를 통해서 답을 찾아내야 한다.
라이언이 할 수 있는 경우의 수는 어피치보다 해당 과녁에 많은 화살을 쏴 점수를 얻거나, 0개를 쏴서 해당 과녁의 점수를 얻지 못하거나 둘 중에 하나이다.

  1. bfs 함수를 만들어 준다.
    1-1. deque를 만들어 focus(현재 노리는 과녁), 과녁판 현황 배열을 넣어준다.
    ex) q = deque([(0, [0,0,0,0,0,0,0,0,0,0,0])])
    1-2. 쏜 화살 수가 n발일 경우, 점수를 계산하고, 점수 차가 클 경우 return 해줄 배열에 해당 과녁 현황을 배열에 넣어준다.
    1-3. 쏜 화살 수가 n을 넘었을 경우 continue
    1-4. focus가 10인데 쏜 화살 수가 n보다 작을 경우, focus에 남은 화살을 넣고, 해당 과녁 현황을 q에 넣어준다.
    1-5. 그외에 어피치보다 화살을 많이 쏠 경우와 0발을 쏠 경우를 q에 추가해준다.
    1-6. 위 과정을 q에 값이 없어질 때까지 반복한다.
  1. bfs를 통해서 return 받은 배열 안에 값이 없을 경우 [-1]을, 값이 있을 경우 배열의 가장 끝 값을 return 해준다.

from collections import deque

def bfs(n, info):
    res = []
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])]) # 문제 풀이 1-1번
    maxGap = 0

    while q: # 문제 풀이 1-6번
        focus, arrow = q.popleft()
        ryan, apeach = 0, 0
    
        if sum(arrow) == n: # 문제 풀이 1-2번
            for i in range(11):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        apeach += 10-i
                    else:
                        ryan += 10-i
            if ryan > apeach:
                gap = ryan - apeach
                if gap > maxGap:
                    maxGap = gap
                    res.clear()
                    res.append(arrow)
                elif gap == maxGap:
                    res.append(arrow)
        elif sum(arrow) > n: # 문제 풀이 1-3번
            continue
        elif focus == 10: # 문제 풀이 1-4번
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1, tmp))
        else: # 문제 풀이 1-5번
            tmp = arrow.copy()
            tmp[focus] = info[focus] + 1
            q.append((focus+1, tmp))
            tmp2 = arrow.copy()
            tmp2[focus] = 0
            q.append((focus+1, tmp2))
    return res

def solution(n, info):
    winList = bfs(n, info)
# 문제 풀이 2번   
    if not winList:
        return [-1]
    else:
        return winList[-1]
profile
못하는 건 없다. 단지 그만큼 노력을 안 할 뿐이다.

0개의 댓글