문제 정의
숫자 배열 arr을 첫 번째 인수로, 숫자 num을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
배열의 각 숫자는 1부터 13 사이의 값으로, 플레잉 카드의 번호를 나타냅니다. 이때 우리의 목표는 모든 카드를 크기가 num이고, 서로 연속된 숫자로 이루어진 그룹으로 나눌 수 있는지 판별하는 것입니다.
예를 들어 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const arr = [1, 4, 3, 2];
const num = 2;
출력
true
출력 설명
카드들을 [1, 2], [3, 4] 두 개의 그룹으로 재정렬할 수 있으므로 결과는 true입니다. 각 그룹은 크기가 2이고, 그룹 내부의 숫자는 서로 연속됩니다.
접근 방식
이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
먼저 배열을 오름차순으로 정렬한 뒤, 각 숫자의 등장 횟수를 해시 맵(객체)에 기록합니다. 이후 정렬된 순서대로 숫자를 순회하면서, 아직 사용되지 않은 카드(map[n]이 0보다 큰 경우)를 만나면 해당 숫자부터 시작하여 연속된 num개의 카드가 모두 존재하는지 확인합니다. 하나라도 부족하면 그룹을 만들 수 없으므로 false를 반환하고, 성공적으로 그룹을 구성했다면 맵에서 해당 카드들의 개수를 차감합니다.
작은 숫자부터 처리하면 나중에 더 긴 연속 구간을 만들 때 선택지가 제한되지 않으므로, 이 그리디한 선택이 항상 최적의 결과를 보장합니다.
코드 구현
다음은 위 접근 방식을 구현한 전체 코드입니다.
const arr = [1, 4, 3, 2];
const num = 2;
const canRearrange = (arr = [], num = 1) => {
// n부터 시작해 연속된 num개의 카드를 그룹으로 묶을 수 있는지 확인
const find = (map, n, num) => {
let j = 0;
while (j < num) {
if (!map[n + j]) return false;
else map[n + j] -= 1;
j++;
}
return true;
};
let map = {};
arr.sort(function (a, b) { return a - b });
// 각 카드 번호의 등장 횟수 기록
for (let n of arr) {
map[n] = map[n] ? map[n] + 1 : 1;
}
// 남은 카드가 있다면 반드시 그룹의 시작점이므로 검사
for (let n of arr) {
if (map[n] === 0 || find(map, n, num)) continue;
else return false;
}
return true;
};
console.log(canRearrange(arr, num));
실행 결과
true
동작 과정 살펴보기
입력 [1, 4, 3, 2]와 num = 2를 예로 들어 코드의 흐름을 단계별로 살펴보겠습니다.
먼저 배열이 [1, 2, 3, 4]로 정렬되고, 맵에는 각 숫자가 한 번씩 등장했다고 기록됩니다. 이후 순서대로 순회하면서 1부터 시작하는 그룹을 찾는데, 1과 2가 모두 존재하므로 그룹 [1, 2]가 완성되고 맵에서 개수가 차감됩니다. 같은 방식으로 3부터 시작하는 그룹 [3, 4]도 성공적으로 구성됩니다. 모든 카드가 소진되었으므로 최종적으로 true가 반환됩니다.
만약 중간에 연속된 카드가 하나라도 부족하다면 find 함수가 false를 반환하고, 전체 함수 역시 즉시 false를 반환하게 됩니다.
마무리
이 문제는 정렬과 해시 맵을 조합한 대표적인 그리디 알고리즘 예제입니다. 시간 복잡도는 정렬에 O(N log N), 그룹 검사에 O(N × num)이 소요되며, 카드 덱 문제(예: 리트코드 '손에 든 카드로 스트레이트 만들기')와 유사한 유형으로 자주 출제됩니다. 연속된 요소로 그룹을 나누는 변형 문제에도 동일한 접근 방식을 활용할 수 있으니 응용해 보시기 바랍니다.