문제: https://school.programmers.co.kr/learn/courses/30/lessons/258709
풀이(이진 탐색): [프로그래머스] 주사위 굴리기 - 2024 카카오 겨울 인턴십
카카오 공식 문제해설은 이진 탐색을 사용하는 것보다 시간복잡도 측면에서 더 효율적인 방법이 있음을 시사하였고, 답을 구하는 방법으로는 누적합, 투포인터, 이진 탐색 등을 언급하였습니다.
그래서 저는 이진 탐색을 활용했던 부분을 누적합으로 대체하여 시간복잡도를 개선해 보고자 합니다.
리팩토링
시뮬레이션 결과
우선 시뮬레이션 결과를 저장하는 방식을 바꿔 봅시다. 누적합을 활용하려면 우선 결과를 구간으로 나타내야 할 필요가 있습니다.
시뮬레이션 결과의 범위
주사위 N개를 던졌을 때 얻을 수 있는 최대 숫자는 다음과 같습니다.
주사위 1개: 1 이상 100 이하 → 주사위 N개: N 이상 N * 100 이하
따라서, N개의 주사위를 던진다고 했을 때 N * 100 + 1 크기의 배열을 미리 선언하여 답을 저장할 수 있도록 합니다. 배열 요소의 값은 0으로 초기화합니다.
예시
예시로 1, 2, 3, 4, 98, 100의 눈을 가진 주사위 하나를 던졌을 때 얻을 수 있는 결과를 비교해 봅시다.
A 방식으로 기록한 결과는 다음과 같습니다.
[1, 2, 3, 4, 98, 100] // 크기 6^N의 배열B 방식으로 기록한 결과는 다음과 같습니다.
[0, 1, 1, 1, 1, ..., 1, 0, 1] // 크기 N*100 + 1의 배열위의 결과를 나중에 누적합으로 나타내면 아래와 같아집니다.
[0, 1, 2, 3, 4, ..., 5, 5, 6]시뮬레이션 결과 구하기
기존 방식과의 차이는 다음과 같습니다.
- 기존: 빈 배열을 선언한 뒤 주사위를 굴린 모든 결과를 탐색한 순서대로 push합니다.
- 변경: N * 100 + 1 크기의 배열을 선언한 뒤 주사위를 굴린 결과를 인덱스로 하여 result에 접근하여 값을 1 증가시킵니다.
const simulateDiceB = (dices) => {
const N = dices.length;
const result = new Array(N * 100 + 1).fill(0);
const roll = (count = 0, sum = 0) => {
if (N === count){
result[sum]++;
return;
}
const currentDice = dice[dices[count] - 1];
for (let i = 0; i < 6; i++){
roll(count + 1, sum + currentDice[i]);
}
}
roll();
return result;
}기존 방식 코드
const simulateDiceA = (dices) => {
const result = [];
const roll = (count = 0, sum = 0) => {
if (dices.length === count){
result.push(sum);
return;
}
const currentDice = dice[dices[count] - 1];
for (let i = 0; i < 6; i++){
roll(count + 1, sum + currentDice[i]);
}
}
roll();
return result;
}누적합
시뮬레이션 결과 구하기를 통해 얻어진 배열을 누적합 배열로 바꿉니다. 이 때, B를 시뮬레이션한 결과만 바꿔 줍니다.
누적합 만드는 법
const resultB = [1, 2, 3];
for (let i = 1; i < resultB.length; i++){
resultB[i] += resultB[i-1];
}
resultB; // [1, 3, 6]1부터 배열의 길이 - 1 인덱스까지 순회하며 i번째 값에 i - 1번째 값을 더합니다. 위의 과정을 수행하고 난 뒤의 i번째 요소는 0부터 i번째까지의 합계를 나타냅니다.
만들어진 누적합 배열로 이진 탐색 과정을 대체할 수 있습니다.
- 기존: resultA의 모든 요소(num)에 대하여 이진 탐색을 수행하여 num보다 작은 숫자가 가지는 가장 큰 인덱스 탐색
- 변경: resultA의 모든 요소(num)에 대하여 누적합 배열의 num - 1 인덱스에 접근
매번 이진 탐색을 호출하여 인덱스를 헤매는 대신 resultB[num - 1]의 값을 바로 더합니다.
주어진 조건에서 num이 0이 될 가능성은 없으니 num - 1로 인덱싱하는 것에 대해 따로 예외처리는 진행하지 않겠습니다.
const countWins = (resultA, resultB) => {
let count = 0;
for (let num of resultA){
count += resultB[num - 1];
}
return count;
}승리 횟수를 누적하는 로직을 성공적으로 대체하였습니다.
효율 비교
승리 횟수 누적과 관련한 부분만 한정해서 생각해 보겠습니다.
메모리
한번에 던지는 주사위의 개수가 4개 이상이 될 때부터 B 방식이 더 효율적입니다.
| N | 2 | 4 | 6 | 8 | 10 |
| N/2 | 1 | 2 | 3 | 4 | 5 |
| A | 6 | 36 | 216 | 1296 | 7776 |
| B | 101 | 201 | 301 | 401 | 501 |
시간
주사위의 개수 N과 구분하기 위해 주사위 N개를 던져 얻는 결과의 개수를 M이라고 하겠습니다.
이진 탐색을 사용한 로직의 경우, 이진탐색을 수행하기 위한 결과 B의 정렬에 O(MlogM)이 소요되며, 이진 탐색 자체도 O(logM)이 배열 요소 전체 횟수만큼 수행되므로 O(MlogM)이 됩니다.
최대 1초 이상 소요되었습니다.
누적합을 사용한 로직은 배열에 결과를 저장할 때 O(M)이 소요되며, 누적할 때 최대 500번 정도 계산하는 건 큰 의미를 가지지 않습니다.
이진 탐색에 비하여 상당히 개선된 실행 시간을 얻었습니다.
코드
이진 탐색
function solution(dice) {
const N = dice.length;
const combination = [];
const tmp = [];
const dfs = (N, prev = 0) => {
if (tmp.length === N/2){
combination.push([...tmp]);
return;
}
for (let i = prev + 1; i <= N; i++){
tmp.push(i);
dfs(N, i);
tmp.pop();
}
}
dfs(N);
const simulateAllDices = (dices) => {
const result = [];
const roll = (count = 0, sum = 0) => {
if (dices.length === count){
result.push(sum);
return;
}
const currentDice = dice[dices[count] - 1];
for (let i = 0; i < 6; i++){
roll(count + 1, sum + currentDice[i]);
}
}
roll();
return result;
}
const binarySearch = (arr, target) => {
let left = 0;
let right = arr.length;
let result = -1;
while (left <= right){
let mid = Math.floor((left + right)/2);
if (arr[mid] < target){
left = mid + 1;
result = mid;
} else {
right = mid - 1;
}
}
return result + 1;
}
const countWins = (resultA, resultB) => {
resultB.sort((a, b) => a - b);
let count = 0;
for (let num of resultA){
count += binarySearch(resultB, num);
}
return count;
}
const allDices = new Array(N).fill().map((_, i) => i + 1);
let maxWin = -1;
let maxIdx = -1;
for (let i = 0; i < combination.length; i++){
const A = combination[i];
const aSet = new Set(A);
const B = allDices.filter(v => !aSet.has(v));
const resultA = simulateAllDices(A);
const resultB = simulateAllDices(B);
const wins = countWins(resultA, resultB);
if (wins > maxWin){
maxWin = wins;
maxIdx = i;
}
}
return combination[maxIdx];
}
누적합
function solution(dice) {
const N = dice.length;
const combination = [];
const tmp = [];
const dfs = (N, prev = 0) => {
if (tmp.length === N/2){
combination.push([...tmp]);
return;
}
for (let i = prev + 1; i <= N; i++){
tmp.push(i);
dfs(N, i);
tmp.pop();
}
}
dfs(N);
const simulateAllDices = (dices) => {
const result = [];
const roll = (count = 0, sum = 0) => {
if (dices.length === count){
result.push(sum);
return;
}
const currentDice = dice[dices[count] - 1];
for (let i = 0; i < 6; i++){
roll(count + 1, sum + currentDice[i]);
}
}
roll();
return result;
}
// 시뮬레이션 결과 변경
const simulateDiceB = (dices) => {
const N = dices.length;
const result = new Array(N * 100 + 1).fill(0);
const roll = (count = 0, sum = 0) => {
if (N === count){
result[sum]++;
return;
}
const currentDice = dice[dices[count] - 1];
for (let i = 0; i < 6; i++){
roll(count + 1, sum + currentDice[i]);
}
}
roll();
return result;
}
// 기존: 이진 탐색 수행 → 변경: 누적합 배열의 값을 바로 활용
const countWins = (resultA, resultB) => {
let count = 0;
for (let num of resultA){
count += resultB[num-1];
}
return count;
}
const allDices = new Array(N).fill().map((_, i) => i + 1);
let maxWin = -1;
let maxIdx = -1;
for (let i = 0; i < combination.length; i++){
const A = combination[i];
const aSet = new Set(A);
const B = allDices.filter(v => !aSet.has(v));
const resultA = simulateAllDices(A);
const resultB = simulateDiceB(B);
// resultB의 결과 누적
for (let i = 1; i < resultB.length; i++){
resultB[i] += resultB[i-1];
}
const wins = countWins(resultA, resultB);
if (wins > maxWin){
maxWin = wins;
maxIdx = i;
}
}
return combination[maxIdx];
}개선 여지
Map 적용 시도
A의 결과를 저장할 때 Map으로 저장하면 승리 횟수를 누적할 때 중복되는 숫자에 대한 반복되는 연산을 줄일 수 있을 것 같습니다.
해보고 오겠습니다.
메모리는 5~6MB 정도 줄었으나 시간은 오히려 더 걸렸습니다. 중복되는 부분은 어느 정도 걸러졌지만 Map을 순회하기 위해 들여야 하는 노력이 생각보다 큰가 봅니다.
A의 결과에도 새로 적용한 방식을 적용
본문에서는 B에만 새로운 방식을 적용했습니다. Map을 사용할 것이 아니라 아예 A의 결과도 변경된 방식으로 100*N + 1 크기의 배열에 저장해 보겠습니다.
최대 7776개의 결과를 최대 501칸짜리 배열에 꾹꾹 눌러 담아 중복을 제거하고 더욱 빠르게 반복을 마칠 수 있게 되었습니다.
// before
const countWins = (resultA, resultB) => {
let count = 0;
for (let num of resultA){
count += resultB[num - 1];
}
return count;
}
// after
const countWins = (resultA, resultB) => {
let count = 0;
for (let i = 0; i < resultA.length; i++){
const num = resultA[i];
if (num){
count += resultB[i - 1] * num;
}
}
return count;
}