📌 Frequency Counters(빈도수 세기 패턴)
여러 개의 문자열이나 배열을 비교해야 할 때, 배열 간에 직접 일치 여부를 확인하지 않고 객체를 만들어 빈도수를 따로 세주기
예제
숫자를 담은 두 개의 배열 arr1, arr2가 주어질 때, arr2에 있는 값들이 arr1의 제곱으로 이루어져 있으면 true, 아니면 false를 return 하시오.
방법 1. Naive한 방식
두 개의 배열을 중첩된 루프를 통해 비교하는 방법
(for 안에 indexOf가 중첩되어 있음)
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
for(let i = 0; i < arr1.length; i++){
let correctIndex = arr2.indexOf(arr1[i] ** 2)
if(correctIndex === -1) {
return false;
}
console.log(arr2);
arr2.splice(correctIndex,1)
}
return true;
}
same([1,2,3,2], [9,1,4,4])방법 2. Frequency counter를 이용한 방식
두 개의 배열을 객체로 세분화하여 각 배열의 요소를 분류하고 비교하는 방법
⭐️ 두 개의 루프(O(n))가 두 개의 중첩된 개별 루프(O(n^2))보다 성능이 훨씬 낫다는 점을 이용한다.
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
let frequencyCounter1 = {}
let frequencyCounter2 = {}
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
}
for(let val of arr2){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
}
console.log(frequencyCounter1);
console.log(frequencyCounter2);
for(let key in frequencyCounter1){
if(!(key ** 2 in frequencyCounter2)){
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
return false
}
}
return true
}
same([1,2,3,2,5], [9,1,4,4,11])연습 문제
두 개의 문자열 str1, str2가 주어질 때, str2가 str1의 anagram인지 판별하기.(str2를 조합해서 str2를 만들 수 있는가)
-
조건 : Frequency Counter 방식으로 풀기
각각의 counter를 만들고 빈도수를 세서 비교해준다.
function validAnagram(str1,str2){
// 길이가 다른 경우 false, 둘 다 빈 문자열이면 true
if(str1.length !== str2.length) return false;
if(!str1 && !str2) return true;
// 각각 counter 만들기
let counter1 = {};
let counter2 = {};
// 빈도수 구하기
for(let n of str1){
counter1[n] = (counter1[n] || 0) + 1;
}
for(let n of str2){
counter2[n] = (counter2[n] || 0) + 1;
}
// 비교하기
for(let key in counter1){
if(counter1[key] !== counter2[key]){
return false;
}
}
return true;
}
validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true counter를 하나만 만들어서 str1을 먼저 넣고, 그 후에 str2의 존재여부를 확인하는 방법도 있다.
(좀 더 단순해짐)
function validAnagram(first, second) {
if (first.length !== second.length) {
return false;
}
const lookup = {};
for (let i = 0; i < first.length; i++) {
let letter = first[i];
// if letter exists, increment, otherwise set to 1
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
for (let i = 0; i < second.length; i++) {
let letter = second[i];
// can't find letter or letter is zero then it's not an anagram
if (!lookup[letter]) {
return false;
} else {
lookup[letter] -= 1;
}
}
return true;
}
validAnagram('anagrams', 'nagaramm')
📌 Multiple Pointers(다중 포인터 패턴)
배열에서 여러개의 포인터를 이용해 특정 방향으로 이동하며 답 찾기
예제
정렬된 배열이 주어질 때, 처음으로 합이 0이 되는 쌍을 찾아서 반환하기.
(존재하지 않으면 undefined 반환하기)
방법 1. Naive한 방식
중첩된 for문으로 배열을 돌며 하나씩 전부 체크하기
- 시간 복잡도 : O(n^2)
- 공간 복잡도 : O(1)
function sumZero(arr){
for(let i = 0; i < arr.length; i++){
for(let j = i+1; j < arr.length; j++){
if(arr[i] + arr[j] === 0){
return [arr[i], arr[j]];
}
}
}
}
sumZero([-4,-3,-2,-1,0,1,2,5])방법 2. Multiple pointer를 이용한 방식
가장 작은 값(왼쪽)과 가장 큰 값(오른쪽)을 더해서 0이 되는 경우 찾기
- 왼쪽과 오른쪽에 각각 하나씩 총 두 개의 pointer를 만들어준다.
(여기서 pointer는 index와 같은 의미라고 보면 됨.) - 두 포인터가 가리키는 값의 합이 0이 되면 값을 반환하고, 0보다 크면 오른쪽 pointer를 하나 줄여서 다시 체크하고, 0보다 작으면 왼쪽 pointer를 하나 늘려서 다시 체크한다.
(왼쪽 index가 오른쪽 index보다 작을 때까지 반복)
- 시간 복잡도 : O(n) -> 시간 복잡도 개선됨.
- 공간 복잡도 : O(1)
function sumZero(arr){
let left = 0;
let right = arr.length -1 ;
while(left < right){
let sum = arr[left] + arr[right];
if(sum === 0) {
return [arr[left], arr[right]]
}else if(sum > 0){
right--;
}else{
left++:
}
}
}
sumZero([-4,-3,-2,-1,0,1,2,5])연습 문제
정렬된 배열을 입력 받아서 unique value의 갯수를 return 하기
- 포인터를 두 개 만든다. (
i는 0부터 시작,j는 1부터 시작) - 두 포인터가 가리키는 값이 같으면 i는 그대로 있고 j가 오른쪽으로 한 칸 이동한다.
가리키는 값이 다르면 업데이트 해야 하므로 i의 값이 업데이트 되고, i와 j가 모두 한 칸 오른쪽으로 이동한다. - 마지막으로
i가 unique value의 갯수와 같으므로 i를 return한다.
⭐️ 여기서는 위와 다르게 두 포인터가 같은 방향으로 이동하는 것이 포인트
function countUniqueValues(arr){
let i = 0;
let j = 1;
while(j<=arr.length){
if(arr[i] === arr[j]){
j++;
}else{
arr[i+1] = arr[j];
i++;
j++;
}
}
return i;
}
countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4반복문을 통해 j를 증가시키며 이동하면 더 짧게 나타낼 수 있다.
function countUniqueValues(arr){
if(arr.length === 0) return 0;
var i = 0;
for(var j = 1; j < arr.length; j++){
if(arr[i] !== arr[j]){
i++;
arr[i] = arr[j]
}
}
return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99])📌 Sliding Window(기준점 간 이동 배열 패턴)
연속적인 데이터의 하위 집합을 찾는데 유용함.
(특정 갯수만큼 묶어서 이동시키기)
예제
입력값으로 배열 arr와 숫자 num이 주어질 때, arr을 num개씩 합할 때의 최댓값을 구하시오.
방법 1. naive한 방식
중첩된 반복문을 이용해 i만큼씩 이동하며 j개씩 더하여 더 큰 값을 반환함.
ex. maxSubarraySum([2,6,9,2,1,8,5,6,3],3)
2+6+9
6+9+2
9+2+1
...
주어진 배열과 숫자의 크기가 매우 클 때, 값을 새롭게 계속 더하며 비교하는 방식은 매우 비효율적일 수 있음.
시간 복잡도 : O(n^2)
function maxSubarraySum(arr, num) {
if (num > arr.length){
return null;
}
var max = -Infinity;
for (let i = 0; i < arr.length - num + 1; i ++){
temp = 0;
for (let j = 0; j < num; j++){
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}
maxSubarraySum([2,6,9,2,1,8,5,6,3],3)방법 2. sliding window를 이용한 방식
처음부터 끝까지 num개의 숫자를 계속 새롭게 더하는 것이 아닌, 처음 num개의 합계를 유지한 상태로 앞에 숫자를 하나 빼고 뒤에 숫자를 하나 더하며 이동함.
ex. maxSubarraySum([2,6,9,2,1,8,5,6,3],3)
기본값 : (2+6+9)
(2+6+9) -2 +2 = 6+9+2
(6+9+2) -6 +1 = 9+2+1
(9+2+1) -9 +8 = 2+1+8
...
숫자를 계속 새롭게 더하지 않고, 기본 합계에서 앞,뒤 하나씩만 제어하면서 합계를 구할 수 있게 되어 매우 효율적이다.
반복문을 중첩해서 사용하지 않아도 되기 때문에 시간 복잡도도 단순해진다.
시간 복잡도 : O(n)
function maxSubarraySum(arr, num){
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
maxSubarraySum([2,6,9,2,1,8,5,6,3],3) 📌 Divide and Conquer(분할 정복 패턴)
실제 사용하는 문서화된 이름이다.
- 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.
- 큰 데이터셋을 작은 하위셋으로 분할하여 필요한 부분만 탐색하는 방법이다.
- 시간 복잡도를 매우 크게 낮춰줄 수 있다.
분할 정복 알고리즘 : 이진 탐색, 병합 정렬, 퀵 정렬 등
예제
정렬된 배열과 특정 숫자가 주어질 때, 배열에서 해당 숫자의 index를 반환하시오.
- 왼쪽부터 하나씩 살펴보는
선형 탐색
시간 복잡도 : O(N) - 배열을 나누는
이진 탐색
찾는 수가 배열의 중간 지점보다 크면 중간부터 오른쪽으로 탐색, 작으면 중간부터 왼쪽으로 탐색을 할 수 있다.
시간 복잡도 : O(Log(N))
