[일간코테] 주사위 고르기 (Python, Java)

문제 바로가기

프로그래머스

 

문제 해결 과정 정리

아주 호흡이 긴 문제였다. 여러 가지 개념이 섞여 있고, 특히 자바로 풀 때는 call-by-reference, 초기화 문제 등의 오류를 주의해야 한다. 이 문제를 풀기 위한 접근 방식을 차근차근 정리해 보자.

---

1. 완전 탐색의 기본 아이디어

문제를 해결하기 위해 가장 먼저 떠오르는 방식은 완전 탐색이다. 문제를 단계별로 나누면 다음과 같다:

1. A가 선택할 주사위 조합 구하기
   • nnn개의 주사위에서 n/2n/2n/2개를 선택하는 모든 조합을 생성한다.
2. A와 B의 주사위 점수 합 리스트 구하기
   • A와 B 각각의 주사위를 굴려 나올 수 있는 점수 합 리스트를 계산한다.
3. A가 이기는 경우의 수 계산
   • A의 점수 합 리스트와 B의 점수 합 리스트를 비교하여, A가 이길 경우의 수를 계산한다.

---

2. 완전 탐색의 한계

• 각 주사위는 6개의 면을 가지고 있으므로, 모든 가능한 경우의 수는 6^n이다.
• 예를 들어, n=10일 경우: 6^10=60,466,176,000
• 이는 너무 많은 경우의 수로 시간 초과가 발생한다.

따라서, A와 B의 결과를 독립적으로 계산한 후(6^(n/2)), 최종적으로 비교만 수행하는 방식으로 접근해야 한다.

---

3. 독립적 계산으로 시간 복잡도 줄이기

• A와 B의 주사위를 나눠 각각 점수 합 리스트를 계산한 뒤, 비교 과정을 수행하면 시간 복잡도를 줄일 수 있다.
• 하지만 여기서도 문제가 있다. 만약 A와 B의 점수 리스트를 각각 N개, M개라고 하면,
  • 모든 값을 하나하나 비교할 경우: O(N×M)
  • 예를 들어, N=M=36일 경우: 36×36=1,296
• N과 M이 더 커진다면 비효율적일 수 있다.

---

4. 효율적인 비교를 위한 핵심 아이디어

문제의 본질은 [A 주사위 점수 합>B 주사위 점수 합] 을 만족하는 경우의 수를 찾는 것이다.

• 핵심은 A의 점수 합 리스트의 각 원소에 대해, 그 값보다 작은 B의 점수 합 리스트의 원소 개수를 빠르게 찾는 것이다.
• 이를 위해:
  1. B의 점수 합 리스트를 정렬한다.
  2. 각 A의 점수에 대해, B의 점수 리스트에서 이분 탐색을 사용하여 효율적으로 비교한다.

이렇게 하면 시간 복잡도를 크게 줄일 수 있다.

---

5. 정리

• 완전 탐색 방식은 6^n로 인해 비효율적이다.
• A와 B의 주사위를 나눠 독립적으로 점수를 계산한 뒤, 효율적인 비교 과정을 수행해야 한다.
• 비교 과정에서는:
  1. B의 점수 리스트를 정렬한다.
  2. 이분 탐색을 통해 A의 특정 점수보다 작은 B의 점수 개수를 빠르게 찾는다.
     

from itertools import combinations
from itertools import product
from bisect import bisect_left

def calculate_sums(dice):
    # 가능한 주사위 굴림 결과 모든 합을 계산하여 반환
    sums = []
    for comb in product(*dice):
        sums.append(sum(comb))
    return sums

def solution(dice):
    answer = []
    
    n = len(dice)
    half = n // 2
    
    # A가 가지는 주사위 번호 조합
    all_combs = list(combinations(range(n), half))
    
    # 승리확률이 가장 높은 주사위 조합을 구해야 한다.
    max_win_cnt = -1
    best_comb = []
    
    for comb in all_combs:
        # 번호대로 A 주사위, B 주사위 나누기
        a_dice = [dice[i] for i in comb]
        b_dice = [dice[i] for i in range(n) if i not in comb]
        
        # A, B 각 주사위 눈 합 계산
        a_sums = calculate_sums(a_dice)
        b_sums = calculate_sums(b_dice)
        
        b_sums.sort()
        
        # A 승리 수 계산 (A의 각 합에 대해 B의 합이 작은 개수 찾기)
        win_cnt = 0
        for a_sum in a_sums:
            win_cnt += bisect_left(b_sums, a_sum)
        
        # 승리 수가 가장 많은 조합 찾기
        if win_cnt > max_win_cnt:
            max_win_cnt = win_cnt
            best_comb = comb
    
    return [i + 1 for i in best_comb]

 

자바 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    static int n;
    static int half;
    static List<List<Integer>> allCombs = new ArrayList<>();
    
    static int maxWinCount = -1;
    static List<Integer> bestComb = new ArrayList<>();

    public int[] solution(int[][] dice) {
        
        n = dice.length;
        half = n / 2;
        
        // A가 가질 수 있는 주사위 번호 조합
        combinations(n, half, 0, new ArrayList<>());
        
        /*
        System.out.println("All Combinations:");
        for (int i = 0; i < allCombs.size(); i++) {
            System.out.print("Combination " + (i + 1) + ": ");
            System.out.println(allCombs.get(i));
        }
        */
        for (List<Integer> comb : allCombs) {
            // A와 B 주사위 분리
            List<int[]> aDice = new ArrayList<>();
            List<int[]> bDice = new ArrayList<>();
            
            for (int i = 0; i < n; i++) {
                if (comb.contains(i))
                    aDice.add(dice[i]);
                else
                    bDice.add(dice[i]);
            }
            
            // A와 B의 각 주사위 눈 합 계산
            List<Integer> aSums = calculateSums(aDice);
            List<Integer> bSums = calculateSums(bDice);
            Collections.sort(bSums);
            
            // A 승리수 계산
            int winCount = 0;
            for (int aSum : aSums)
                winCount += bisectLeft(bSums, aSum);
            
            // 승리 수가 가장 많은 조합 찾기
            if (winCount > maxWinCount) {
                maxWinCount = winCount;
                bestComb = new ArrayList<>(comb);
            }            
        }
        return bestComb.stream().mapToInt(idx -> idx + 1).toArray();

    }
    
    public static void combinations(int n, int r, int start, List<Integer> curList) {
        if (curList.size() == r) { // 종료 조건
            allCombs.add(new ArrayList<>(curList));
            return;
        }
        for (int i = start; i < n; i++) {
            curList.add(i);
            combinations(n, r, i + 1, curList);
            curList.remove(curList.size()-1);
        }
    }
    
    public static List<Integer> calculateSums(List<int[]> dice) {
        List<Integer> sums = new ArrayList<>();
        getCartesianProductHelper(dice, 0, 0, sums);
        return sums;
    }
    private static void getCartesianProductHelper(List<int[]> dice, int idx, int currSum, List<Integer> sums) {
        if (idx == dice.size()) {
            sums.add(currSum);
            return;
        }
        for (int val : dice.get(idx)) {
            getCartesianProductHelper(dice, idx + 1, currSum + val, sums);
        }
    }
    
    public static int bisectLeft(List<Integer> sortedList, int target) {
        int left = 0;
        int right = sortedList.size();
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (sortedList.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;

    }
}

---

 

문제 해결 과정에서 추가적으로 주의 깊게 본 사항

이 문제를 풀면서 특히 자바로 직접 구현한 bisectLeft, combinations, product의 중요성을 실감했다. 이러한 기능들은 파이썬에서는 기본 라이브러리로 제공되지만, 자바에서는 직접 구현해야 했기 때문에 다음과 같은 점에 주의해야 했다.

🔶 핵심 코드 템플릿

1. bisectLeft 구현 (정렬된 리스트에서 특정 값보다 작은 원소 개수 찾기)

public static int bisectLeft(List<Integer> sortedList, int target) {
    int left = 0;
    int right = sortedList.size();
    while (left < right) {
        int mid = (left + right) / 2;
        if (sortedList.get(mid) < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left; // target보다 작은 원소의 개수
}

주의점:

• 정렬된 리스트에서만 동작.
• 종료 조건에서 left가 삽입 위치를 가리킴.

2. combinations 구현 (A와 B가 가져갈 주사위 조합 생성)

public static void combinations(int n, int r, int start, List<Integer> curList, List<List<Integer>> result) {
    if (curList.size() == r) {
        result.add(new ArrayList<>(curList)); // 조합 저장
        return;
    }
    for (int i = start; i < n; i++) {
        curList.add(i);
        combinations(n, r, i + 1, curList, result);
        curList.remove(curList.size() - 1); // 백트래킹
    }
}

주의점:

• 조합 생성 시 중복 방지를 위해 start 인덱스를 사용.
• 참조 관리 문제를 방지하기 위해 new ArrayList<>(curList)로 복사본 저장.

3. product 구현 (주사위 모든 면의 조합 생성)

public static void getCartesianProduct(List<int[]> dice, int idx, int currSum, List<Integer> sums) {
    if (idx == dice.size()) {
        sums.add(currSum);
        return;
    }
    for (int val : dice.get(idx)) {
        getCartesianProduct(dice, idx + 1, currSum + val, sums);
    }
}

주의점:

• currSum을 유지하며 재귀 호출로 각 조합의 합을 계산.
• 종료 조건에서 결과 리스트에 합을 추가.