//Write a function called sameFrequency.
//Given two positive integers, find out if the two numbers have the same frequency of digits.
//Your solution MUST have the following complexities:
//Time: O(N)
//Sample Input:
sameFrequency(182, 281) //true
sameFrequency(34, 14) //false
sameFrequency(3589578, 5879385) //true
sameFrequency(22, 222) //false
function sameFrequency(num1, num2){
let str1 = String(num1).split(''), str2 = String(num2).split(''); // ['1', '8', '2'], ['2', '8', '1']
if (str1.length !== str2.length) return false; //예외처리
let str1Obj = str1.reduce((prev, curr) => { // str1 을 객체에 담기
prev[curr] = curr in prev ? prev[curr]+=1 : 1;
return prev;
}, {}); // {1: 1, 2: 1, 8: 1}
for (let x of str2) { // str2와 str1Obj 비교
if (str1Obj[x]) str1Obj[x]--;
else return false;
}
return true;
}
모범답
function sameFrequency(num1, num2){
let strNum1 = num1.toString();
let strNum2 = num2.toString();
if(strNum1.length !== strNum2.length) return false;
let countNum1 = {};
let countNum2 = {};
for(let i = 0; i < strNum1.length; i++){
countNum1[strNum1[i]] = (countNum1[strNum1[i]] || 0) + 1
}
for(let j = 0; j < strNum1.length; j++){
countNum2[strNum2[j]] = (countNum2[strNum2[j]] || 0) + 1
}
for(let key in countNum1){
if(countNum1[key] !== countNum2[key]) return false;
}
return true;
}
Q2. Frequency Counter / Multiple Pointers - areThereDuplicates
//Implement a function called, areThereDupliccates
//which accepts a variable number of arguments,
//and checks whether are any duplicates among the arguments passed in.
//You can solve this using the frequency counter pattern OR the multiple pointers pattern.
//Examples:
areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true
areThereDuplicates('a', 'b', 'c', 'a') //true
//Restrictions:
//Time - O(n)
//Space - O(n)
//Bonus:
//Time - O(n log n)
//Space - O(1)
function areThereDuplicates(...rest) {
let arr = rest.join('').split('') // ['1', '2', '2']
let obj = arr.reduce((prev, curr) => {
if (curr in prev) prev[curr] += 1
else prev[curr] = 1
return prev
}, {}) // {1: 1, 2: 2}
for (let x in obj) {
if (obj[x] !== 1) return true
}
return false
}
// areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true
// areThereDuplicates('a', 'b', 'c', 'a') //true
TIP - 인자를 받지 않는 함수에 인자 넣어 호출해도, arguments 객체를 쓰면 호출된 함수의 인자에 접근 가능하다.
arguments란?함수 내부에서 액세스할 수 있는 배열과 유사한 객체이다
function argumentTest() {
for (let x in arguments) {
console.log(`key: ${x}, value: ${arguments[x]}`)
}
}
argumentTest(1, 2, 2)
//key: 0, value: 1
//key: 1, value: 2
//key: 2, value: 2
모범답 -areThereDuplicates 솔루션 (Frequency Counter- 빈도 수 세기)
function areThereDuplicates() {
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;
}
모범답 - areThereDuplicates 솔루션 (Multiple Pointers - 다중 포인터)
function areThereDuplicates(...args) {
// Two pointers
args.sort((a,b) => a > b);
let start = 0;
let next = 1;
while(next < args.length){
if(args[start] === args[next]){
return true
}
start++
next++
}
return false
}
모범답 -areThereDuplicates One Liner 솔루션
function areThereDuplicates() {
return new Set(arguments).size !== arguments.length;
}
Q3. Multiple Pointers - averagePair
//Write a function called averagePair.
//Given a sorted array of integers and a target average,
//determine if there is a pair of values in the array where the average of the pair equals the target average.
//There may be more than one pair that matches the average target.
//Bonus Constraints:
//Time: O(N)
//Space: O(1)
//Sampe Input:
averagePair([1,2,3], 2.5) //true
averagePair([1,3,3,5,6,7,10,12,19], 8) //true
averagePair([-1,0,3,4,5,6], 4.1) //false
averagePair([], 4) //false
function averagePair(arr, avg) {
for (let start = 0; start < arr.length-1; start++) {
let next = start+1;
while (next < arr.length) {
if ((arr[start] + arr[next])/2 === avg) {
console.log(`start: ${start+1}, next: ${next+1}, ${arr[start]}+${arr[next]}`);
return true;
}
next++;
}
}
return false;
}
모범 답
function averagePair(arr, num){
let start = 0
let end = arr.length-1;
while(start < end){
let avg = (arr[start]+arr[end]) / 2
if(avg === num) return true;
else if(avg < num) start++
else end--
}
return false;
}
averagePair([1,3,3,5,6,7,10,12,19], 8) //true
와.. 이렇게 간단한 거 였다니.. 나는 생각도 안나던데.. 조금 더 고민해보고 문제에 접근할것.
Q4. Multiple Pointers - isSubsequence
//Write a function called isSubsequence which takes in two strings and
//checks whether the characters in the first form a subsequence of the characters in the second string.
//In other words, the function should check
//whether the characters in the first string appear somewhere in the second string,
//without their order changing.
isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)
//Your solution MUST have AT LEAST the following complexities:
//Time Complexity - O(N+M)
//Space Complexity - O(1)
function isSubsequence(str1, str2) {
var i = 0;
var j = 0;
if (!str1) return true;
while (j < str2.length) {
if (str2[j] === str1[i]) i++;
if (i === str1.length) return true;
j++;
}
return false;
}
//Given an array of integers and a number,
//write a function called maxSubarraySum,
//which finds the maximum sum of a subarray with the length of
//the number passed to the function.
//Note that a subarray must consist of consecutive elements from the original array.
//In the first example below, [100, 200, 300] is a subarray of the original array, but [100, 300] is not.
maxSubarraySum([100, 200, 300, 400], 2) // 700
maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4) // 39
maxSubarraySum([-3, 4, 0, -2, 6, -1], 2) // 5
maxSubarraySum([3, -2, 7, -4, 1, -1, 4, -2, 1], 2) // 5
maxSubarraySum([2, 3], 3) // null
//Constraints:
//Time Complexity - O(N)
//Space Complexity - O(1)
function maxSubarraySum(arr, size){
if (arr.length < size) return null; //예외처리
let max = 0, sum = 0;
for (let i = 0; i < size; i++) { //윈도우 생성
sum += arr[i];
}
max = sum;
for (let i = size; i < arr.length; i++) { //윈도우 이동
sum += arr[i];
sum -= arr[i-size];
max = Math.max(sum, max); //윈도우 이동할때마다 max값 최신화
}
return max;
}
Q6. Sliding Window -minSubArrayLen
//Write a function called minSubArrayLen ,which a accepts two parameters - an array of positve integers and a positive integer.
//This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn't one, return 0 instead.
// 합계가 함수에 전달된 정수보다 크거나 같은 연속된 하위 배열(subarray)의 최소 길이를 반환한다.
// 없는 경우 대신 0을 반환하시오.
//Example:
minSubArrayLen([2,3,1,2,4,3], 7) // 2-> because [4, 3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> -> because [5, 4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10], 39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10], 55) // 5
minSubArrayLen([4,3,3,8,1,2,3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10], 95) // 0
//Time Complexity - O(n)
//Space COmplexity - O(1)
function minSubArrayLen(nums, sum) {
let total = 0
let start = 0
let end = 0
let minLen = Infinity
while (start < nums.length) {
// if current window doesn't add up to the given sum then
// move the window to right
if (total < sum && end < nums.length) {
total += nums[end]
end++
}
// if current window adds up to at least the sum given then
// we can shrink the window
else if (total >= sum) {
minLen = Math.min(minLen, end - start)
total -= nums[start]
start++
}
// current total less than required total but we reach the end, need this or else we'll be in an infinite loop
else {
break
}
}
return minLen === Infinity ? 0 : minLen
}
Q7. Sliding Window -findLongestSubstring - 어려움 주의
//Write a function called findLonestSubstring
//, which accepts a string and returns the length of the longest substring
//with all distinct chaaracters.
findLonestSubstring,('') // 0
findLonestSubstring,('rithmschool') // 7
findLonestSubstring,('thisisawesome') // 6
findLonestSubstring,('thecatinthehat') // 7
findLonestSubstring,('bbbbbb') // 1
findLonestSubstring,('longestsubstring') // 8
function findLongestSubstring(str) {
let longest = 0;
let seen = {};
let start = 0;
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (seen[char]) { // 1)
start = Math.max(start, seen[char]);
}
// index - beginning of substring + 1 (to include current in count)
longest = Math.max(longest, i - start + 1); // 2)
// store the index of the next char so as to not double count
seen[char] = i + 1; // 3)
}
return longest;
}
findLongestSubstring('abcdbefghi') // 8
// 'c d b e f g h i' -> 8
1) str의 요소값이 seen 객체에서 발견되면 해당 key의 value값을 start에 재할당 한다.
2) longest 값은 1)조건으로 start 값이 바뀌면 2)에서 longest값은 그대로이고 1)의 조건이 아닐때는 longest 값이 증가 할 수 있다.
