문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
예제 입력 1
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
예제 출력 1
3 0 0 1 2 0 0 2주어진 숫자의 범위가 -10,000,000와 10,000,000의 사이이므로 선형 탐색으로 접근하면 시간 초과가 발생한다.
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, A, M, B] = input.map(v => v.split(' ').map(Number));
// 정렬
A.sort((a, b) => a - b);
const findFisrtIdx = (arr, target) => {
for(let i = 0; i < arr.length - 1; i++) {
if(arr[i] === target) return i;
}
return -1;
}
const findLastIdx = (arr, target) => {
for(let i = arr.length - 1; i >= 0; i--) {
if(arr[i] === target) return 1;
}
return -1;
}
const binarySearch = (arr, target) => {
const firstIdx = findFirstIdx(arr, target);
const lastIdx = findLastIndex(arr, target);
if(firstIdx === -1 && lastIdx === -1) {
return 0;
} else {
return lastIdx - firstIdx + 1;
}
}
const result = B.map(b => binarySerach(A, b));
console.log(result)풀이
Ver 1. Map 활용
문제 풀이 방식
배열의 중복 요소 문제이므로 Set 객체 대신 Map 객체를 활용할 수 있다.
- N 배열의 요소를 Map 객체의 key로 저장한다.
- 중복 개수를 세는 것이므로 이미 존재한 수 or 처음 확인된 수를 판별
- 단, 이때 화살표 형태로 기입(ex.
6 => 1)되어서 결과 배열을 따로 만들어야 한다.
- 결과 배열 만들기
- N 배열에 있는 b 요소는 map 객체에 담긴 값 그대로, 없는 경우 0을 넣는다.
- 참고로 Map은 순서를 보장하기 때문에 추가 작업 없이 요소를 순회해주면 된다.
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, A, M, B] = input.map(v => v.split(' ').map(Number));
// Set 객체는 요소의 중복 불가, Map 객체는 중복 가능.
const map = new Map();
// 1. N 배열의 key를 Map 객체에 세팅한다.
A.forEach(a => {
if(map.has(a)) {
map.set(a, map.get(a) + 1);
} else {
map.set(a, 1);
}
});
// 2. 화살표로 저장되므로 결과 배열 새로 가공.
// 이때 A에 없는 b 요소는 0을 넣는다.
let result = [];
B.forEach(b => {
if(map.get(b)) {
result.push(map.get(b));
} else {
result.push(0);
}
})
console.log(result.join(' '));Map 객체
get,set,delete,clear메서드를 사용해 요소를 관리한다.
특징
- 키-값 쌍 저장
-
자바스크립트의 일반적인 객체와 유사
-
BUT key로 다양한 데이터 유형을 사용할 수 있으며, 순서가 보장된다.
- 그래서 요소를 추가하거나 제거할 때도 편리함.
- cf. 자바스크립트 객체는 key가 문자열이고, 순서가 보장되지 않는다.
// 배열 요소를 key로 만들고, value는 0으로 통일 const objA = A.reduce((acc, cur) => ({...acc, [cur]: 0}), {}); // { '2': 0, '3': 0, '6': 0, '7': 0, '10': 0, '-10': 0 }
-
- 요소의 개수 추적 시 용이
- 요소를 key로 사용하여 그 개수를 value에 담는 로직
- 객체보다 요소 추가/제거가 편리
- 순서가 보장되므로 요소를 추가하거나 제거할 때 편리
- WeakMap과 함께 사용 가능
WeakMap은 key로 객체만 허용, 객체에 대한 얕은 참조를 유지하므로 메모리 누수 방지에 효과적
Map 객체를 사용하면 소요시간이 훨씬 적게 걸린다. 하지만 메모리 면에서는 while문이 조금 더 효과적이다.
Ver 2. 인덱스를 구하고 while문 활용
이진 탐색
정렬된 배열에서 특정 요소를 찾을 때, 배열을 반씩 쪼개면서 찾는 방법
이진 탐색 사용법(로직)
- 시작 인덱스과 끝 인덱스 설정
- 중간 인덱스 계산
- 시작 인덱스 + 끝 인덱스 / 2
- 중간 값 비교
- 중간 인덱스 값과 찾고자 하는 값(target)을 비교
- 중간 값 === 타겟 : 중간 인덱스 반환
- 중간 값 > target : 끝 인덱스를 중간 인덱스 - 1로 설정 → 왼쪽 부분배열에서 탐색
- 중간 값 < target : 시작 인덱스를 중간 인덱스 + 1로 설정 → 오른쪽 부분배열에서 탐색
- 중간 인덱스 값과 찾고자 하는 값(target)을 비교
- 반복
- 시작 인덱스가 끝 인덱스보다 작거나 같을 때까지 위 과정 반복
문제 풀이 방식
이 문제에서는 중복된 값이 나오므로 단순히 배열을 반씩 쪼개는 접근이 어렵다.
- 요소의 첫번째 인덱스를 구한다.
- 첫번째 인덱스의 기본값은 -1(false)
- while문으로 부분 배열이 동일해질 때까지 반복한다.
- 포함된 요소를 찾으면, 왼쪽 부분 배열(=더 작은 인덱스 범위)에서 재탐색 한다.
- 중복 요소가 있으므로, 해당 요소의 마지막 인덱스도 구한다.
- 첫번째 인덱스 구하기와 동일 조건이되, 포함된 요소는 오른쪽 부분 배열(=더 큰 인덱스 범위)에서 재탐색 한다.
마지막 인덱스 - 첫번째 인덱스 + 1로 중복 요소의 개수를 구한다.
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, A, M, B] = input.map(v => v.split(' ').map(Number));
A.sort((a, b) => a - b);
const binaryFirstIdx = (arr, target, left, right) => {
let firstIdx = -1;
while(left <= right) {
const mid = Math.floor((left + right) / 2);
if(arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
firstIdx = mid;
right = mid - 1; // 더 작은 인덱스 범위 재탐색
}
}
return firstIdx;
}
const binaryLastIdx = (arr, target, left, right) => {
let lastIdx = -1;
while(left <= right) {
const mid = Math.floor((left + right) / 2);
if(arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
lastIdx = mid;
left = mid + 1; // 더 큰 인덱스 범위 재탐색
}
}
return lastIdx;
}
const binarySearch = (arr, target) => {
const firstIdx = binaryFirstIdx(arr, target, 0, arr.length - 1);
const lastIdx = binaryLastIdx(arr, target, 0, arr.length - 1);
if(firstIdx === -1 && lastIdx === -1) {
return 0;
} else {
return lastIdx - firstIdx + 1;
}
}
const result = B.map(b => binarySearch(A, b));
console.log(result.join(' '));인덱스 탐색 함수는 딱 한 부분만 다르고 나머지는 동일하다.
이를 함수 하나로 묶어주면 아래와 같다.
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, A, M, B] = input.map(v => v.split(' ').map(Number));
A.sort((a, b) => a - b);
const searchIndex = (arr, target, left, right, findFirst) => {
let resultIdx = -1;
while(left <= right) {
const mid = Math.floor((left + right) / 2);
if(arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
resultIdx = mid;
if(findFirst) {
right = mid - 1; // 왼쪽 부분 배열 탐색
} else {
left = mid + 1; // 오른쪽 부분 배열 탐색
}
}
}
return resultIdx;
}
const binarySearch = (arr, target) => {
const firstIdx = searchIndex(arr, target, 0, arr.length - 1, true);
const lastIdx = searchIndex(arr, target, 0, arr.length - 1, false);
if(firstIdx === -1 && lastIdx === -1) {
return 0;
} else {
return lastIdx - firstIdx + 1;
}
}
const result = B.map(b => binarySearch(A, b));
console.log(result.join(' '));정리
하지만 if 조건으로 true, false를 구분하게 되면 메모리와 성능 모두 각기 다른 함수로 분리했을 때보다 사용량이 많아진다. 코드를 간결하게 짜는 것을 목적으로 둔다면 의미가 있겠지만..
차라리 Map을 사용하는 게 가장 소요 시간이 적고, 인덱스를 이진 탐색으로 찾는 방식은 메모리 면에서 효율적이므로 둘 중 하나가 낫다고 생각한다.
일단 해보는 편