문제 설명
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 방법
• 접근 방식
◦ 라이언이 어피치를 가장 큰 점수로 차이로 어피치를 이길 수 있는 경우를 구해야 하는 문제이다.
- 점수차이가 나는데 특별한 수학적 규칙이 없고, 라이언이 화살을 어떻게 쏘는가 그 결과에 달려있다.
- 화살을 쏠 수 있는 모든 경우의 수를 구하고, 그 결과를 비교해 점수차의 최댓값을 구하는 문제이다.
◦ 보통 여러가지 경우의 수에 대한 결과를 비교할 땐 BFS를 사용하는게 편하다. 이 문제도 마찬가지!
• 핵심 아이디어
◦ 10점 ~ 0점 과녁을 순회하면서, 각 점수 과녁에서 라이언이 할 수 있는 선택은 2가지이다.
- 화살을 쏘지 않고 아껴둔다. (사용한 화살 : 0개)
- 어피치가 쏜 화살보다 1개 더 쏜다. (사용한 화살 : 어피치가 쏜 화살 +1개)
◦ 과녁은 10점 ~ 0점 총 11개 이고, 선택은 2가지 이니까 총 2의 11제곱에 대한 경우의 수를 자식 노드가 2개인 이진트리로 집계한 후
결과를 비교하면 된다.
• 알고리즘
◦ 이진트리 BFS
- 각 점수 과녁을 순회하면서 화살을 쏘거나, 쏘지 않거나로 자식 노드를 확장해 나간다.
- 노드 확장 종료 조건 = 화살을 다 쐈음 or (10점~0점 과녁 순으로 순회할 때)현재 과녁이 마지막 과녁임
- 현재 과녁이 마지막 과녁인 경우, 남은 화살을 전부 쏜다.
- 또한 어피치보다 무조건 1개 더 쏘는 상황이 반복되다보면 라이언이 쏠 수 있는 화살 개수보다 더 쏘게되는 상황이
발생할 수 있다. 이는 경기상에서 고려하지 않는 상황이므로, 이 케이스는 무시하는 로직을 추가해 줘야 한다.
- 노드 확장이 종료되면 그 케이스의 라이언과 어피치의 점수 차이를 구한다.
- 모든 경우의 수를 돌면서, 점수 차이가 최대가 되는 값을 계속 업데이트한다.
파이썬 코드
def solution(n, info):
# set variables
bfs = [(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])]
maxScore = 0
answer = []
while(bfs):
# 현재 쏘려는 점수, 과녁 현황
idx, arrowList = bfs.pop(0)
# 종료 조건1 : 화살을 모두 쏜 경우
if(sum(arrowList) == n):
apeach, lion = 0, 0
# 점수 차이 집계
for i in range(11):
if(arrowList[i]+info[i] == 0):
continue
if(arrowList[i] <= info[i]):
apeach += 10 - i
else:
lion += 10 - i
# 라이언이 이긴 경우 : 점수 차이 최댓값 업데이트
if apeach < lion:
if maxScore > (lion - apeach):
continue
if maxScore <= (lion - apeach):
maxScore = lion - apeach
answer = arrowList.copy()
# 종료 조건2 : 화살을 오버해서 쏜 경우 (무시)
elif(sum(arrowList) > n):
continue
# 종료 조건3 : 마지막 과녁인데 화살이 남은 경우 (남은 화살을 다 쏜다)
elif(idx == 10):
arrowList[10] = n - sum(arrowList)
bfs.append((-1,arrowList))
# 경기 진행중
else:
# 어피치보다 1발 더 쏘기
temp = arrowList.copy()
temp[idx] = info[idx]+1
bfs.append((idx+1, temp))
# 쏘지 않기
temp = arrowList.copy()
temp[idx] = 0
bfs.append((idx+1, temp))
# return answer
if(not answer):
return [-1]
return answer'CodingTest' 카테고리의 다른 글
| [2022 KAKAO BLIND RECRUITMENT] 양과 늑대 (0) | 2022.09.23 |
|---|---|
| [2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금 (0) | 2022.09.23 |
