문제의 흐름을 파악하면 크게 3단계로 나눌 수 있다.
1. 모든 주사위 조합을 구한다.
2. 조합들을 비교하여 , A가 B를 이기는 가장 높은 확률의 주사위 조합을 구한다.
3. 가장 확률이 높은 주사위 번호를 오름차순으로 정렬한다.
결국 주사위 n/2개를 뽑은 A가 나머지 주사위를 고른 B를 가장 많이 이기는 주사위 n/2개의 주사위 조합을 구하면 된다.
실제 코딩테스트를 볼 때 위의 단계까진 생각했으나 구현에서 막혔다.
시간 복잡도를 계산하면 n의 범위는 10이므로 A가 가질 수 있는 최대 주사위의 개수는 5개, 5개의 주사위에서 나올 수 있는 주사위의 합은 최대 6*6*6*6*6= 7776개이다.
A가 B를 이기는 횟수를 구하기 위해 A가 가질 수 있는 주사위의 합의 개수, B가 가질 수 있는 주사위의 합의 개수를 계산해보자.
(A가 가질 수 있는 주사위의 합의 개수) * (B가 가질 수 있는 주사위의 합의 개수) = 7776 * 7776 = 60466176 로
시간 초과가 일어날 수 있다.
이를 위해 이분탐색을 통해 N*N이 아닌 N*logN으로 시간복잡도를 줄일 수 있다.
소스코드는 아래와 같다.
from itertools import combinations, product
from bisect import bisect_left
'''
모든 주사위 조합을 구한다.
조합들을 비교하여 , 가장 높은 확률이 높은 주사위 조합을 구한다.
가장 확률이 높은 주사위 번호를 오름차순으로 정렬한다.
'''
def get_dice_comb(dice):
dice_comb = list(combinations(dice,len(dice)//2))
return dice_comb
def get_best_comb(dice_comb,dice):
best_per = 0
best_comb = dice_comb[0][0]
for idx in range(len(dice_comb)):
first_comb, second_comb = dice_comb[idx], get_second_comb(dice_comb[idx],dice)
if cal_win_per(first_comb,second_comb) > best_per:
best_per, best_comb = cal_win_per(first_comb,second_comb), first_comb
return find_dice_num(best_comb,dice)
def find_dice_num(best_comb,dice):
ret = []
for idx in range(len(dice)):
for comb in best_comb:
if comb == dice[idx]:
ret.append(idx+1)
break
return ret
def get_second_comb(dice_comb,dice):
ret = []
for comb in dice:
if comb not in dice_comb:
ret.append(comb)
return ret
def cal_win_per(first_comb, second_comb):
cnt = 0
first_cases, second_cases = get_comb_cases(first_comb), get_comb_cases(second_comb)
for first_case in first_cases:
cnt += get_win_cnt(first_case,second_cases)
return cnt
def get_comb_cases(comb):
ret = []
for prod in list(product(*comb)):
ret.append(sum(prod))
return sorted(ret)
def get_win_cnt(first_case,second_cases):
return bisect_left(second_cases,first_case)
def solution(dice):
answer = []
dice_comb = get_dice_comb(dice)
answer = get_best_comb(dice_comb,dice)
return answer
변수명을 per이라고 했지만 나오는 경우의 수는 조합마다 같으므로 얼마나 이기느냐만 체크하면 된다.
이분탐색은 파이썬에서 제공하는 bisect_left를 사용하였다.
복잡해보이지만 알고리즘은 이분탐색만 들어간 문제다.
주사위 번호 찾기, 주사위 조합에서 나올 수 있는 합 계산 등 지문을 꼼꼼히 읽어야 빨리 풀 수 있는 문제인 것 같다.
'문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP 산 모양 타일링 (0) | 2024.03.20 |
---|---|
[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP n+1 카드게임 (0) | 2024.03.20 |
[프로그래머스 문제풀이]2023 KAKAO BLIND RECRUITMENT 표현 가능한 이진트리 (0) | 2023.02.28 |
[프로그래머스 문제풀이] 코딩 테스트 준비 (1) | 2022.08.23 |
[프로그래머스 문제풀이] 두 큐 합 같게 만들기 (0) | 2022.08.23 |