프로그래머스 - 주사위 고르기

https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스

 

1. 2024 KAKAO WINTER INTERNSHIP 문제

 

처음 풀 때

각 원소들을 반복문으로 돌려 다른 원소를 이길 수 있는지 판단하여 count 개수를 세고

주사위별로 count를 합쳐 비교하려 했으나 테스트케이스 7개를 통과하지 못했다.

 

그래서 product를 이용하여 여러 리스트의 조합을 구하고

이진트리로 이길 수 있는 원소들의 개수에 대해 파악했다.

 

[[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]]

해당 input으로 예를 들어보면

 

1. 주사위의 순서 조합을 구한다.

(0,1) (0,2) (0,3) (1,2) (1,3) ...........

인덱스에 해당하는 주사위의 요소들을 

temp_list_1과 나머지 주사위 temp_list_2 에 넣어준다.

인덱스 조합이 (0,1)인 경우로 예를 들면

temp_list_1 = [[1,2,3,4,5,6], [3,3,3,3,4,4]]

temp_list_2 = [[1,3,3,4,4,4], [1,1,4,4,5,5]]

값이 들어간다.

 

2. temp_list_1와 temp_list_2의 중복 순열의 합을 구해준다.

temp_list_1 -> [4,4,4,4,5,5,5,5,5,5,6,6............]

temp_list_2 -> [2,2,5,5,6,6,4,4,7,7,8,8.............]

 

3. temp_list_2를 정렬한 후 temp_list_1의 요소를 하나씩 빼와서 이진탐색을 진행한다.

 

4. count로 가장 큰 값을 비교해 나간다.

from itertools import combinations, product
import bisect
def solution(dice):
    idx_list = list(combinations([i for i in range(0,len(dice))], len(dice)//2))
    answer = []
    max_count = float('-inf')
    for i in idx_list:
        temp_list_1 = []
        temp_list_2 = []
        for j in range(0,len(dice)):
            if j in i:
                temp_list_1.append(dice[j])
            else:
                temp_list_2.append(dice[j])
        count =0
        sum_prodict_1 = [sum(i) for i in list(product(*temp_list_1))]
        sum_prodict_2 = sorted([sum(i) for i in list(product(*temp_list_2))])
        for p in sum_prodict_1:
            count += bisect.bisect_left(sum_prodict_2, p)
        if max_count < count:
            max_count = count
            answer = i
    answer = list(answer)
    for i in range(0,len(answer)):
        answer[i] += 1
    return answer

19번부터 오래 걸린다.

딕셔너리를 이용해서 비교했던 데이터에 대해 저장해 가면

더 시간을 줄일 수 있지 않을까 생각한다.