[프로그래머스] 주사위 고르기(java)

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

프로그래머스

예전에 시도했다가 시간초과가 떴던 문제이다.

사실 이전에 풀 때도 시간초과가 날 거라고 거의 확신하고 푼 문제였기에 이번에 시간이 남아서 다시 풀어보았다.

 

핵심

이번 문제는 구현, 조합, 이분탐색을 사용해야 한다.

내가 맨 처음 접근한 방법은 완전탐색인데 이는 10개 중 5개의 주사위를 고르는 방법 10C5와 각각의 주사위의 합 6^5과 나머지 주사위들의 합인 6^5를 전부 비교해야 하기에 약 100억이 나오게 된다.

따라서 이를 이분탐색을 활용하여 각 값의 요소가 다른 주사위의 합 리스트에서 어디에 위치하는지 찾으면서 해결하였다.

 

 

정답 코드

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

class Solution5 {

    private List<Integer> answer = new ArrayList<>();
    private boolean[] visited;
    private int max = 0;

    public int[] solution(int[][] dice) {
        visited = new boolean[dice.length];
        combination(dice, 0, new int[dice.length / 2], -1);

        return answer.stream()
                .mapToInt(i -> i + 1)
                .toArray();
    }

    private void combination(int[][] dice, int index, int[] now, int pre) {
        if (index == dice.length / 2) {
            List<Integer> firstDice = getSumOfDice(dice, now);

            int[] remainDice = findRemainDice(now);
            List<Integer> secondDice = getSumOfDice(dice, remainDice);

            Collections.sort(firstDice);
            Collections.sort(secondDice);

            int result = 0;

            for (int f : firstDice) {
                result += findIndex(f, secondDice);
            }

            if (max < result) {
                max = result;
                answer.clear();
                Arrays.stream(now).forEach(i -> answer.add(i));
            }
            return;
        }

        for (int i = 0; i < dice.length; i++) {
            if (!visited[i] && i > pre) {
                visited[i] = true;
                now[index] = i;
                combination(dice, index + 1, now, i);
                visited[i] = false;
            }
        }
    }

    private int[] findRemainDice(int[] now) {
        int[] dice = new int[now.length];

        int index = 0;
        for (int i = 0; i < now.length * 2; i++) {
            if (!contains(now, i)) {
                dice[index++] = i;
            }
        }

        return dice;
    }

    private boolean contains(int[] now, int i) {
        return Arrays.stream(now)
                .anyMatch(n -> n == i);
    }

    private List<Integer> getSumOfDice(int[][] dice, int[] now) {
        List<Integer> sum = new ArrayList<>();
        addSum(dice, now, sum, 0, 0);
        return sum;
    }

    private void addSum(int[][] dice, int[] now, List<Integer> list, int index, int sum) {
        if (index == now.length) {
            list.add(sum);
            return;
        }

        for (int i = 0; i < 6; i++) {
            addSum(dice, now, list, index + 1, sum + dice[now[index]][i]);
        }
    }

    private int findIndex(int now, List<Integer> list) {
        int left = 0;
        int right = list.size();

        while (left + 1 < right) {
            int mid = (left + right) / 2;

            if (list.get(mid) < now) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

 

해설

우선 조합을 사용하는데 효율적으로 중복되는 값을 선택하지 않기 위해 visited와 pre라는 변수를 사용하였다.

visited는 첫 번째 주사위, 첫 번째 주사위 선택을 방지하기 위함이고,

pre는 첫 번째 주사위, 세 번째 세 번째 주사위 이후에 세 번째 주사위 첫 번째 주사위를 선택하는 경우를 막기 위함이다.

 

이후 조합을 사용하여 주사위를 선택한 이후에 이 주사위들의 합을 구한다.

ex) #1, #3 vs #2, #4 이후에 첫 번째 주사위들의 합 요소를 돌면서 이분탐색을 통해 어디에 위치하는지 값을 구한다.

 

제일 많이 위치가 증가된 주사위를 답으로 선정한다.

 

 

배운 점

요즘 프로그래머스를 푸는데 남은 문제가 전부 다 어려워서 무엇을 풀지 고민하고 있었다.

그러다 예전에 풀지 못했던 문제가 올라와서 시도하게 되었다.

그때는 정확히 어느 포인트를 최적화해야 할지에 대한 확신이 없었는데, 

이번에 풀 때는 값을 비교하는 로직이 최적화되어야 한다는 판단을 가지고 풀어서 성공하게 되었다.

 

어려운 문제를 만나면 좀 더 논리적으로 접근하려는 습관을 들이자.

 

자바로 푼사람이 내가 두 번째이기에 매우 기분이 좋았다.