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

문제 설명

문제 링크

풀이

나는 이 문제를 특별한 풀이가 아닌 완전탐색 + 구현을 통해서 풀었다. 전체적인 풀이를 먼저 보면 완전탐색을 통해 A가 얻는 주사위의 조합을 모두 계산하고, 각 조합마다 A가 B를 이기는 횟수를 계산하여 그 횟수가 가장 클 때의 조합을 찾는 것이다.

좀 더 자세히 보면 combi리스트에 A가 얻을 수 있는 모든 주사위 조합을 저장한다.

List<Set<Integer>> combi = new ArrayList<>();

public void combination(Set<Integer> idxSet, int idx, int n) {
	if (idxSet.size() == n/2) {
    	combi.add(idxSet);
        return;
    }
    if (idx == n) {
        return;
    }

	Set<Integer> newIdxSet = new HashSet<>(idxSet);
	newIdxSet.add(idx);
	combination(newIdxSet, idx+1, n);
	combination(idxSet, idx+1, n);
}

이후 A가 만든 조합을 aSet, 이에 따라 만들어지는 B의조합을 bSet이라고 하자. aSet으로 만들 수 있는 점수(k)를 계산하고, A[k] += 1 해주자.(여기서 A와 B의 크기가 501인 이유는 n은 최대 10이고, 따라서 aSet의 크기는 최대 5이다. 근데 주사위 값의 크기가 최대 100이므로, 만들 수 있는 점수의 최대값은 500이 된다.) 즉 A[k]는 aSet에서 k를 만들 수 있는 상황의 개수이다. B에도 똑같이 하여 B배열을 완성시키자. 이를 해주는 게 makeArray()메서드인데, set에 만약 {1,2}가 들어있다면, dice[1]의 값들과 dice[2]의 값들 중 각각 하나씩 뽑아서 더하는 함수이다.

이렇게 A와 B를 모두 완성시키면 각각의 배열에는 k값을 만들 수 있는 조합 주사위 값 조합의 개수가 저장되어있다. 즉 A[k]=3이면 aSet으로는 k값을 총3개 만들 수 있다는 것이다. 그러면 만약 B가 k를 만들었을 때 A가 이기는 경우는 A가 k보다 큰 값을 가지면 된다. 이를 위해 A를 모두 누적합으로 바꿔주자. A[i] += A[i-1] 이러면 A가 k보다 큰 값을 가지는 경우의 수를 A[500] - A[k]이다. 그러면 (B가 k를 만드는 경우의 수) * (A가 k보다 큰값을 가지는경우의 수)를 하면 k에 B가 k를 만들었을 때 A가 이기는 총 경우의 수를 구할 수 있다. 그러면 B가 구할 수 있는 모든 수를 k로 하여 만들어진 값이 A가 총 이기는 경우의 수이다. 이 값이 최대일 때의 aSet이 정답이된다(정렬해서).

for (Set<Integer> aSet : combi) {//aSet: A가 선택한 주사위들
	Set<Integer> bSet = new HashSet<>();

	for (int i = 0; i < dice.length; i++) {
    	if (!aSet.contains(i)) {
        	bSet.add(i);
        }
    }
    // A가 선택한 주사위들로 만들 수 있는 수들의 개수.  A[i]는 A가 선택한 주사위들로 i를 만들 수 있는 개수
    int[] A = new int[501]; // n은 최대 10이므로, A는 최대 5개의 주사위를 선택하고 주사위의 값은 최대 100. 따라서 최대크기는 500
    int[] B = new int[501];
    makeArray(A, aSet, 0);
    makeArray(B, bSet, 0);

	// A 누적합으로 전환 A[i]는 1~i까지의 가능한 조합의 개수
    for (int i = 1; i <= 500; i++) {
    	A[i] += A[i - 1];
	}

	int tmp = 0;
    for (int i = 0; i <= 500; i++) {
    	if (B[i] != 0) { // B가 i를 만들었을 때 A는 i보다 큰 값이어야 한다. 즉 i보다 큰 A값의 개수 * B가 i를 만드는 경우의 수
        	tmp += B[i] * (A[500] - A[i]);
        }
	}
    if (tmp > mx) {
    	int i = 0;
        for (int num : aSet) {
        	answer[i++] = num + 1;
		}
        mx = tmp;
        Arrays.sort(answer);
	}
}

public void makeArray(int[] C, Set<Integer> set, int sum) {
	if (set.size() == 0) {
    	C[sum]++;
        return;
	}

	Iterator<Integer> it = set.iterator();
    while (it.hasNext()) {
    	int idx = it.next();
        Set<Integer> newSet = new HashSet<>(set);
        newSet.remove(idx);
        for (int num : dice[idx]) {
        	makeArray(C, newSet, sum + num);
		}
        break; // dice의 어떤 인덱스부터 더할지는 중요하지 않다. 결국 반복문이 아니라 set에서 아무거나 빼서 재귀를 돌리면 된다. 
	}
}

전체 코드

package simulation.level3;

import java.util.*;

class PGS_주사위고르기 {
    List<Set<Integer>> combi = new ArrayList<>(); // A가 선택한 주사위들의 조합
    int[][] dice;

    public int[] solution(int[][] dice) {
        int[] answer = new int[dice.length / 2];
        this.dice = dice;

        combination(new HashSet<>(), 0, dice.length); // A가 선택한 주사위 조합 만들기

        int mx = 0;
        for (Set<Integer> aSet : combi) {//aSet: A가 선택한 주사위들
            Set<Integer> bSet = new HashSet<>();

            for (int i = 0; i < dice.length; i++) {
                if (!aSet.contains(i)) {
                    bSet.add(i);
                }
            }
            // A가 선택한 주사위들로 만들 수 있는 수들의 개수.  A[i]는 A가 선택한 주사위들로 i를 만들 수 있는 개수
            int[] A = new int[501]; // n은 최대 10이므로, A는 최대 5개의 주사위를 선택하고 주사위의 값은 최대 100. 따라서 최대크기는 500
            int[] B = new int[501];
            makeArray(A, aSet, 0);
            makeArray(B, bSet, 0);

            // A 누적합으로 전환 A[i]는 1~i까지의 가능한 조합의 개수
            for (int i = 1; i <= 500; i++) {
                A[i] += A[i - 1];
            }

            int tmp = 0;
            for (int i = 0; i <= 500; i++) {
                if (B[i] != 0) { // B가 i를 만들었을 때 A는 i보다 큰 값이어야 한다. 즉 i보다 큰 A값의 개수 * B가 i를 만드는 경우의 수
                    tmp += B[i] * (A[500] - A[i]);
                }
            }
            if (tmp > mx) {
                int i = 0;
                for (int num : aSet) {
                    answer[i++] = num + 1;
                }
                mx = tmp;
                Arrays.sort(answer);

            }
        }

        return answer;
    }

    public void combination(Set<Integer> idxSet, int idx, int n) {
        if (idxSet.size() == n / 2) {
            combi.add(idxSet);
            return;
        }
        if (idx == n) {
            return;
        }

        Set<Integer> newIdxSet = new HashSet<>(idxSet);
        newIdxSet.add(idx);
        combination(newIdxSet, idx + 1, n);
        combination(idxSet, idx + 1, n);
    }

    public void makeArray(int[] C, Set<Integer> set, int sum) {
        if (set.size() == 0) {
            C[sum]++;
            return;
        }

        Iterator<Integer> it = set.iterator();
        while (it.hasNext()) {
            int idx = it.next();
            Set<Integer> newSet = new HashSet<>(set);
            newSet.remove(idx);
            for (int num : dice[idx]) {
                makeArray(C, newSet, sum + num);
            }
            break;
        }
    }
}

회고

이 문제에서 가장 중요한 능력은 구현력이랑 시간복잡도 계산력이다. 누구나 완전탐색을 이용하면 풀 수 있다는 것을 알면서도, 왠지 시간초과가 날 것이라고 생각하여 해당 풀이로 풀지 않을 수 있다. 그렇기 때문에 문제의 입력 조건을 잘 보고 시간복잡도를 계산해 봄으로써 풀이가 맞는지 틀린지 대략적으로 알 수 있다.
이 문제의 제한사항으로 n(dice의 길이)가 10이하이고, dice[i]의 길이는 6이라는 것이다. 이를 통해 완전탐색의 시간 복잡도를 계산해 보자. 먼저 A가 만들 수 있는 주사위 조합의 개수는 10C5 = 252이다. 그리고 각 조합에 따라 만들 수 있는 수들을 계산하는건 최대 6^5 = 7776이다. A와 B에 대해서 모두 계산해야 하므로 26^5 = 약 15000. 즉 252 15000 = 약 3백만.
자바의 경우 약 1초에 1억번의 연산이 가능하므로 해당 풀이로 풀어도 된다는 것을 알 수 있다.