프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
from collections import deque
def solution(n, info):
answer = []
max_score = 0
# 10~0점까지 라이언 화살 개수 배열, 현재 점수
q = deque([([0 for _ in range(11)], 10)])
while q:
arr, score = q.popleft()
if sum(arr) == n: # 남은 화살 모두 소진
# 점수 계산
apeach, lion = 0, 0
for i in range(11):
if info[i] == 0 and arr[i] == 0: # 둘 다 한 발도 못 맞춘 경우
continue
else: # 점수 나옴
if info[i] >= arr[i]:
apeach += 10 - i
else:
lion += 10 - i
if lion > apeach: # 라이언이 이김
if max_score <= (lion - apeach): # 점수차 최대이면 저장
max_score = lion - apeach
answer = []
answer = [i for i in arr]
elif sum(arr) > n: # 화살 넘치게 쏨
continue
elif score == 0: # 남은 화살 다 소진 못 하고 0점까지
new_arr = [i for i in arr]
new_arr[10] = n - sum(new_arr)
q.append((new_arr, 0))
else:
# 어피치가 점수 가져감 (라이언이 0개 맞추기)
new_arr = [i for i in arr]
q.append((new_arr, score - 1))
# 라이언이 점수 가져감 (어피치보다 1개 더 맞추기)
new_arr2 = [i for i in arr]
new_arr2[10-score] = info[10-score] + 1
q.append((new_arr2, score - 1))
if not answer:
return [-1]
else:
return answer
BFS를 이용하여 풀이하였다.
q에 라이언이 점수별로 쏜 화살 개수를 저장할 배열과 현재 배점을 튜플로 넣어준다. 그 후 q가 빌 때까지 아래의 과정을 반복한다.
- arr의 원소들의 합이 n이라면 라이언이 쏠 수 있는 화살을 모두 소진한 경우이다. 그러니 이 때 라이언과 어피치의 점수를 계산하여 둘의 점수차가 이전까지 계산된 점수차보다 크거나 같다면 answer를 지금의 화살 개수 배열 리스트로 갱신해준다. 왜 클 때가 아니라 크거나 같을 때이냐면 점수차가 같다면 더 낮은 점수를 많이 맞힌 경우를 return하라는 조건이 있기 때문이다. 이 코드에서 보면 더 낮은 점수를 많이 맞춘 경우가 q에 더 늦게 추가되기 때문에 나중에 나오는 경우가 더 낮은 점수를 많이 맞춘 경우이다. 따라서 같은 점수차일지라도 가장 마지막에 나온 배열이 정답이 되도록 하였다.
그리고 라이언과 어피치의 총점 계산 시 주의할 점은 둘 다 화살을 맞추지 않았을 경우 그 누구도 점수를 가져가지 않는다는 조건이 있다는 점이다. - arr의 원소들의 합이 n을 초과한다면 이는 라이언이 화살을 넘치게 쏜 경우이므로 유효하지 않은 리스트이다. continue하여 버리면 된다.
- score가 0이 되었다면 화살을 다 소진하지 못하고 0점까지 온 경우이다. 이 경우에는 남은 화살을 다 0점에 맞춘 것으로 하고 q에 추가해준다.
- 위의 3가지 경우에 해당되지 않는다면 그냥 라이언이 화살을 쏘면 된다. 라이언이 어피치보다 n점에 맞춘 화살 개수가 많기만 하면 n점을 가져갈 수 있으므로 화살을 아끼기 위해서는 어피치보다 1개 더 맞추거나 0개 맞추는 경우만 고려하면 된다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 프로그래머스 단어 변환 (0) | 2022.10.21 |
---|---|
[Python/파이썬] 프로그래머스 네트워크 (0) | 2022.10.14 |
[Python/파이썬] 백준 16724번 피리 부는 사나이 (1) | 2022.10.06 |
[Python/파이썬] 백준 14503번 로봇 청소기 (0) | 2022.10.02 |
[Python/파이썬] 백준 5014번 스타트링크 (0) | 2022.09.27 |