문제해결 패턴 1 / 빈도수 세기 패턴
빈도수 세기 패턴 예제
인풋: 두 배열
아웃풋: 배열2가 배열1의 제곱인지(순서는 상관 없고 빈도가 같아야한다) boolean
📂 순진한 접근법 O(n²)
arr1의 길이만큼 for 루프
arr2에 indexOf 메서드로 arr1의 제곱 값이 있는지 확인하고 return true. splice로 지움
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;
arr2.splice(correctIndex,1)
}
return true;
}
✔️ 중첩 루프보다 루프 두개로 따로 쓰는 게 낫다.
이 방법은 시간 복잡도가 O(n²)으로, 효율적이지 않다.
이중배열이라면 input 배열의 길이가 1000일 경우, 1000을 1000번, 결국 100만 번 반복해야 한다.
📂 for loop O(n)
문자열의 내용을 분석할 때 객체를 사용하면 다른 객체의 형태와 신속하게 비교할 수 있다.
두 개의 배열을 객체로 세분화하여 각 배열의 요소들을 분류한 다음 각 배열을 비교한다.
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 arr1){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) +1
}
for(let key in frequencyCounter1){
if(!(key**2 in frequencyCounter2)){ //fre1의 key**2가 fre2에 있나
return false;
}
if(frequencyCounter2[key**2] !== frequencyCounter1[key]){ //두 키의 value가 같은지 확인
return false;
}
}
return true;
}
✔️ OR Operater
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) +1
}왼쪽 || 오른쪽
왼쪽이 false인 경우 오른쪽 리턴
frequensyCounte1의 키 val에 값을 할당하는데,
키 값이 undefined(flase)이면 0을 할당하고 +1,
키 값이 있으면 거기에 +1
📂 빈도 수 세기 패턴으로 Anagram 해결
입력된 두 문자열이 서로의 아나그램이면 true
문자열은 모두 소문자. 여백 없음.
✔️ 경계 조건이 무엇인지, 여백을 처리해야하는지 항상 먼저 묻기
✔️ 루프를 적용해 만든 객체를 사용하고 중첩되기 않은 두 번째 루프를 사용하여 O(n) 시간 복잡도를 유지
내가 쓴 코드. 앞서 배운 빈도 수 세기를 그대로 적용했고, 틀렸다ㅎ
// 수도 코드
길이가 다르면 false 리턴
str1, 2 객체를 만들어 준다.
각 키-값을 반복하며 srt[val]:회수 객체 만들어줌
객체1의 키가 2에도 있는지,
두 값은 일치하는지 확인
일치하지 않으면 false
위 모든 조건에 걸리지 않았으면 true 리턴한다.function validAnagram(str1, str2){
// add whatever parameters you deem necessary - good luck!
if(str1.length !== str2.length) return false;
if(str1.length === 0 && str1.length === 0) return true;
let obj1 = {};
let obj2 = {};
for(item of str1){
obj1[item] = (obj1[item] || 0) +1;
}
for(item of str2){
obj2[item] = (obj2[item] || 0) +1;
}
for(key in obj1){
if(!(key in obj2)) return false;
if(obj1[key] !== obj2[key]) return false;
}
return true;
}
📎 Anagram O(n)
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];
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
for(let i=0; i < second.length; i++){
let letter = second[i];
if(!lookup[letter]){
return false;
} else {
lookup[letter] -=1 ;
}
}
return true;
}
처음에는 왜 신나게 -1 하더니 마지막에 true를 리턴하나, 이해를 못했다.
이해하고 보니 아주 재미있는 해결방법.
유효하지 않은 값, 조건을 걸러내 간소화 하기
if(first.length !== second.length){
return false;
}첫번째 문자열(first)와 두번째 문자열(second)의 길이가 다르다면 Anagram일 수 없다.
바로 false를 리턴한다.
비교할 객체 만들기
const lookup = {};
for(let i=0; i<first.length; i++){
let letter = first[i];
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}빈 객체(lookup)를 선언한다.
객체에 first의 요소가 키로 있다면 값에 +1, 없다면 {요소: 1} 로 키값 쌍을 만들어준다.
lookup은 first를 구성하는 모든 글자가 키로, 빈도가 값으로 키값 쌍을 이루고 있다.
일치 여부 판별하기 ( 0 === false !)
for(let i=0; i < second.length; i++){
let letter = second[i];
if(!lookup[letter]){
return false;
} else {
lookup[letter] -=1 ;
}
}
return true;만들어진 lookup에 letter 키가 없으면 바로 false를 리턴한다.
키가 있다면 -1 해준다.
이렇게 요소, 빈도 모두 일치한다면 모든 요소의 값은 0이 된다.
만약 요소가 다르거나, 빈도가 다르다면 if 조건문에서 false가 리턴된다.
validAnagram('dawnhee', 'dawnhoe')예를 들어, 'dawnhee'와 'dawnhoe'가 인수로 전달된 경우.
두번째 인수인 'dawnhoe'의 5번째 요소인 'o'의 차례에서, lookup[o]가 undefined이기 때문에 false를 리턴한다.
validAnagram('seohee', 'heesoo')'seohee'와 'heesoo'가 인수인 경우,
두번째 인수인 'heesoo'의 네번째 요소 'o'의 차례에서 lookup[o]가 값을 가지고 있으므로, 조건문을 충족하지 못하고 -1을 해준다.
그럼, {o: 0} 인 상태이다.
마지막으로, 'heesoo'의 다섯번째 요소 'o'의 차례에서 lookup[o]은 0(false)이기 때문에, 조건문을 충족하여 리턴 false가 된다.
📂 빈도 수 세기 연습 문제
파라미터로 두 숫자를 받아, 요소들의 빈도가 같은지 확인한다.
function sameFrequency(aa,bb){
// 두 숫자를 string으로 만든다
// 개수가 다르면 false
// 빈 객체 두개를 만든다
// 0부터 시작해 요소의 길이 전까지 돌리는데,
// 객체 안에 키가 없으면 만들어서 값으로 1을 할당한다,
// 있으면 값에 +1 한다.
// 반복문으로 두 객체의 키 값이 같은지 확인한다.
const a = aa.toString();
const b = bb.toString();
if(a.length !== b.length) return false;
let obj1 = {};
let obj2 = {};
for(let i=0; i<a.length; i++){
obj1[a[i]] = (obj1[a[i]] || 0) +1
}
for(let i=0; i<b.length; i++){
obj2[b[i]] = (obj2[b[i]] || 0) +1
}
for(let key in obj1){
if(obj1[key] !== obj2[key]) return false
}
return true;
}
areThereDuplicates(1,2,3) // false
areThereDuplicates(2,2,3,4) // true
areThereDuplicates('a', 'b', 'g', 'b') // true
function areThereDuplicates(arguments) {
// 빈도 수 세기 패턴으로 풀기.
//객체 하나를 만든다
// 키값이 이미 있으면 true를 리턴한다.
let collection = {}
for(let val in arguments){
collection[arguments[val]] = (collection[arguments[val]] || 0) + 1
}
for(let key in collection){
if(collection[key] > 1) return true
}
return false;
}