중복된 항목이 포함된 숫자 배열이 주어졌을 때, 이 배열을 입력받아 동일한 값들을 하나의 하위 배열(subarray)로 묶은 새로운 배열을 반환하는 함수를 작성하는 것이 목표입니다.
문제 예시
예를 들어 다음과 같은 경우를 생각해 볼 수 있습니다.
//입력 배열이 다음과 같다면:
const arr = [1, 3, 3, 1];
//출력 결과는 다음과 같아야 합니다:
const output = [[1, 1], [3, 3]];
해결 접근 방식
이 문제는 해시맵(HashMap) 객체를 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 해시맵에 각 숫자 값이 처음 등장했을 때, 해당 값을 첫 번째 요소로 하는 새로운 하위 배열을 생성하고, 그 하위 배열의 인덱스를 해시맵에 저장합니다.
- 이미 해시맵에 존재하는 값이라면, 저장된 인덱스를 이용해 해당 하위 배열에 값을 추가(push)합니다.
for 반복문으로 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)입니다.
구현 코드
const arr = [1, 3, 3, 1];
const groupArray = arr => {
const map = {};
const group = [];
for(let i = 0; i < arr.length; i++){
if(typeof map[arr[i]] === 'number'){
//이미 등장한 값이므로 기존 하위 배열에 추가
group[map[arr[i]]].push(arr[i]);
} else {
//push 메서드는 배열의 새로운 길이를 반환하며,
//새로 추가된 요소의 인덱스는 '길이 - 1'입니다
map[arr[i]] = group.push([arr[i]])-1;
}
};
return group;
}
console.log(groupArray(arr));
코드 설명
여기서 눈여겨볼 부분은 group.push([arr[i]])-1 입니다. JavaScript의 push() 메서드는 요소를 추가한 후 배열의 새로운 길이(length)를 반환하기 때문에, 여기서 1을 빼면 방금 추가된 하위 배열의 실제 인덱스가 됩니다. 이 값을 해시맵에 저장해 두면, 이후 동일한 값이 등장했을 때 바로 해당 하위 배열에 접근할 수 있습니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ [ 1, 1 ], [ 3, 3 ] ]
이처럼 해시맵을 활용하면 배열 내 동일한 요소들을 효율적으로 그룹화할 수 있습니다.