[level 2] 양궁대회

 문제 

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=python3 

프로그래머스

 사용 언어 

Python3

 풀이 과정 

level 2 문제인데... 풀지 못했다😥

이번주에 코딩테스트 스터디에서 백트래킹을 공부한 이후, 이 문제에도 백트래킹을 사용하면 해결될 것 같아 다시 도전해보려고 했다. 그런데 어떻게 시작해야할지 감도 못잡고 실패..ㅎ

 

블로그를 참고하니 역시 완전 탐색 문제가 맞는 것 같고 구현 방법은 combination / BFS / DFS로 나뉘는 것 같았다.

 

나는 초반에 내가 풀고 싶었던 DFS 코드 느낌을 찾아서 약간 수정했다.

점수도 꽤 많이 주는 걸로 봐서 효율성 좋게 통과!

 

 제출 답안 

# 라이언과 어피치가 같은 점수에 같은 개수를 맞히면 어피치 득점
# k점 영역에 몇 개를 맞히든 k점만 획득
# 라이언이 가장 큰 점수 차이로 이길 때의 점수판

from copy import deepcopy
max_diff, max_board = 0, []

def solution(n, info):
    def dfs(ascore, lscore, cnt, idx, board):
        global max_diff, max_board
        if cnt > n:
            return
        if idx > 10:
            diff = lscore - ascore
            if diff > max_diff:
                board[10] = n - cnt
                max_board = board
                max_diff = diff
            return
        if cnt < n:
            board2 = deepcopy(board); board2[10-idx] = info[10-idx] + 1
            dfs(ascore, lscore+idx, cnt+info[10-idx]+1, idx+1, board2)
            
        board1 = deepcopy(board)
        
        if info[10-idx] > 0:
            dfs(ascore+idx, lscore, cnt, idx+1, board1)            
        else:
            dfs(ascore, lscore, cnt, idx+1, board1)
            
    dfs(0, 0, 0, 0, [0]*11)
    return max_board if max_board else [-1]

 

 다른 사람 풀이 

1. BFS

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]

➡ deque와 while을 사용해서 정석 BFS처럼 풀고 조건을 잘 나눈 것 같다. 신기했는데 코드를 돌려보니 속도도 훨씬! 빨랐다. 확실히 DFS보단 BFS가 빠른 것 같다.

 

출처 : https://velog.io/@hygge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%96%91%EA%B6%81%EB%8C%80%ED%9A%8C-2022-KAKAO-BLIND-RECRUITMENT-BFS

 

2. Combination

from itertools import combinations_with_replacement
from collections import Counter

def solution(n, info):
    max_diff, max_comb_cnt = 0, {}

    for comb in combinations_with_replacement(range(11), n):
        cnt = Counter(comb)
        score1, score2 = 0, 0
        for i in range(1, 11):
            if info[10-i] < cnt[i]:
                score1 += i
            elif info[10-i] > 0:
                score2 += i
                
        diff = score1 - score2
        if diff > max_diff:
            max_comb_cnt = cnt
            max_diff = diff
            
    if max_diff > 0:
        answer = [0]*11
        for n in max_comb_cnt:
            answer[10-n] = max_comb_cnt[n] 
        return answer 
    else:
        return [-1]

➡ combination은 combination인데 처음 보는  combination_with_replacement 를 사용했다. 뭔지 궁금해서 찾아보니 iterable에서 원소 개수가 r개인 중복 조합 뽑기라고 한다. 새로운 거 하나 습득! 그런데 역시 예상했던대로 시간이 압도적으로 오래걸렸다. 완전 탐색은 알고리즘을 잘 사용하는 것이 중요한 것 같다!

 

출처 : https://velog.io/@jadenkim5179/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%96%91%EA%B6%81%EB%8C%80%ED%9A%8C 

 

3. DFS

max_num = -1
answer = []
    
def solution(n, info):

    def cal(appeach, lion):
        a_score, l_score = 0, 0
        for i in range(11):
            if appeach[i] == lion[i] == 0: continue
            elif appeach[i] > lion[i]:
                a_score += 10 - i
            else:
                l_score += 10 - i
        return a_score, l_score
    
    def dfs(lion, idx):
        global max_num, answer
        
        if idx == 11:
            a, l = 0, 0
            if sum(lion) == n:
                a, l = cal(info, lion)
            elif sum(lion) < n:
                lion[-1] += (n - sum(lion))
                a, l = cal(info, lion)
            else:
                return
            if a < l:
                if max_num < (l-a):
                    max_num = (l-a)
                    answer = [lion[:]]
                elif max_num == (l-a):
                    answer.append(lion[:])
            return
        
        lion.append(info[idx]+1)
        dfs(lion, idx+1)
        lion.pop()
        
        lion.append(0)
        dfs(lion, idx+1)
        lion.pop()
    
    dfs([], 0)
    if not answer: return [-1]

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

➡ 또다른 DFS를 활용한 풀이인데 정석  백트래킹 에 더 가깝고 코드 이해도 쉬웠다. append와 pop을 이용해 구현해야 했다는 걸 깨달았다. 그리고 같은 DFS를 사용했지만 내가 처음에 제출한 코드보다 훨씬 빨랐다.