[알고리즘] 문제 모음

1. FrequencyCounter

문제

두개의 정수가 주어진다. 두 수가 같은 숫자를 포함하고 있는지 확인하는 함수

조건 : 시간복잡도 O(n)

예시 : 

console.log(sameFrequency(182, 281)); // true
console.log(sameFrequency(34, 14)); // false
console.log(sameFrequency(3589578, 5879385)); // true
console.log(sameFrequency(22, 222)); // false

 

풀이

function sameFrequency(num1, num2) {
  const obj1 = {};
  num1 = num1.toString();
  for (let i = 0; i < num1.length; i++) {
    obj1[num1[i]] ? (obj1[num1[i]] += 1) : (obj1[num1[i]] = 1);
  }
  num2 = num2.toString();
  for (let j = 0; j < num2.length; j++) {
    if (obj1[num2[j]]) {
      obj1[num2[j]] -= 1;
    } else {
      return false;
    }
  }
  return true;
}

2. FequencyCounter

문제

주어진 값들에 중복된 값이 있는지 판별하는 함수 만들기

조건 : 시간복잡도O(n)

예시

console.log(areThereDuplicates(1, 2, 3)); // false
console.log(areThereDuplicates(1, 2, 2)); // true
console.log(areThereDuplicates("a", "b", "c", "a")); // true

풀이

(1) 객체로 풀기

function areThereDuplicates(...arg) {
  const obj = {};
  for (let i = 0; i < arg.length; i++) {
    if (obj[arg[i]]) {
      return true;
    } else {
      obj[arg[i]] = 1;
    }
  }
  return false;
}

(2) 다중 포인터

function areThereDuplicates(...arg) {
  let i = 0;
  let j = 1;
  arg = arg.sort((a, b) => a > b);
  while (j < arg.length) {
    if (arg[i] === arg[j]) {
      return true;
    } else {
      i++;
      j++;
    }
  }
  return false;
}

(3) new Set

function areThereDuplicates() {
  return new Set(arguments).size !== arguments.length;
}

3. MultiplePointers

문제 

배열과, 평균값이 주어진다.

주어진 배열안의 연속된 두수를 더한 평균값이 있는지 확인하는 함수

조건 : 시간복잡도 O(n), 공간복잡도 : O(1)

예시

console.log(averagePair([1, 2, 3], 2.5)); // true
console.log(averagePair([1, 3, 3, 5, 6, 7, 10, 12, 19], 8)); // true
console.log(averagePair([-1, 0, 3, 4, 5, 6], 4.1)); // false
console.log(averagePair([], 4)); // false

풀이

function averagePair(arr, avg) {
  let start = 0;
  let next = arr.length - 1;
  if (next <= 0) return false;

  while (start !== next) {
    if ((arr[start] + arr[next]) / 2 === avg) {
      return true;
    } else if ((arr[start] + arr[next]) / 2 > avg) {
      next -= 1;
    } else {
      start += 1;
    }
  }
  return false;
}

 

4. isSubsequence

문제

2개의 문자열이 주어진다. 첫번째문자열이 2번째 문자열안에 포함되어있는지 확인하는 함수

첫번째 문자열안에 다른 문자열이 들어올수 있지만 순서가 바뀌면 안된다.

조건 : 시간복잡도 O(n), 공간복잡도 O(1)

예시

console.log(isSubsequence("hello", "hello world")); // true
console.log(isSubsequence("sing", "sting")); // true
console.log(isSubsequence("abc", "abracadabra")); // true
console.log(isSubsequence("abc", "acb")); // false (order matters)

풀이

function isSubsequence(str1, str2) {
  let pointer = 0;
  //첫번째 글자 찾기
  //첫번째 다음 글자중 두번째 글자찾기
  // 반복
  for (let i = 0; i < str2.length; i++) {
    if (str1[pointer] === str2[i]) {
      // 마지막글자인경우 return true
      if (pointer === str1.length - 1) {
        return true;
      }
      pointer++;
    }
  }
  return false;
}

5. maxSubarraySum

문제

배열과 숫자가 주어진다.

배열안의 요소들중 주어진 숫자만큼 연속된 수들의 합중 가장큰 합을 찾아  return
조건 : 시간복잡도 O(n)

예시

console.log(maxSubarraySum([100, 200, 300, 400], 2)); // 700
console.log(maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)); // 39
console.log(maxSubarraySum([-3, 4, 0, -2, 6, -1], 2)); // 5
console.log(maxSubarraySum([3, -2, 7, -4, 1, -1, 4, -2, 1], 2)); // 5
console.log(maxSubarraySum([2, 3], 3)); // null

풀이

function maxSubarraySum(arr, length) {
  if (arr.length < length) {
    return null;
  }
  // 초기값
  let maxSum = 0;
  let answer = 0;
  for (let i = 0; i < length; i++) {
    maxSum += arr[i];
    answer += arr[i];
  }
  // 뒤에꺼 더하고 앞에꺼 빼기
  for (let i = length; i < arr.length; i++) {
    maxSum = maxSum - arr[i - length] + arr[i];
    //값이 크면 적용
    if (maxSum > answer) answer = maxSum;
  }
  return answer;
}

6. minSubArrayLen

문제

배열과 숫자가 주어진다

배열의 요소중 연속된 x개의 합이 주어진 숫자보다 크거나 같은 경우가 있다면 x의 최솟값을 return

없다면 0

조건 : 시간복잡도 O(n)

예시

console.log(minSubArrayLen([2, 3, 1, 2, 4, 3], 7)); // 2 -> because [4,3] is the smallest subarray
console.log(minSubArrayLen([2, 1, 6, 5, 4], 9)); // 2 -> because [5,4] is the smallest subarray
console.log(minSubArrayLen([3, 1, 7, 11, 2, 9, 8, 21, 62, 33, 19], 52)); // 1 -> because [62] is greater than 52
console.log(minSubArrayLen([1, 4, 16, 22, 5, 7, 8, 9, 10], 39)); // 3
console.log(minSubArrayLen([1, 4, 16, 22, 5, 7, 8, 9, 10], 55)); // 5
console.log(minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11)); // 2
console.log(minSubArrayLen([1, 4, 16, 22, 5, 7, 8, 9, 10], 95)); // 0

풀이

function minSubArrayLen(arr, num) {
  // n개일때 num와 크기 비교
  let total = 0;
  let start = 0;
  let end = 0;
  let minlen = Infinity;
  while (start < arr.length) {
    if (total < num && end < arr.length) {
      total += arr[end];
      end++;
    } else if (total >= num) {
      minlen = Math.min(minlen, end - start);
      total -= arr[start];
      start++;
    } else {
      break;
    }
  }
  return minlen === Infinity ? 0 : minlen;
}

7. findLongestSubstring

문제

문자열이 주어진다.  문자열안에서 반복되는 글자 사이에 들어가있는 글자 중 가장 긴 갯수를 return

조건 : 시간복잡도 O(n)

예시

console.log(findLongestSubstring("")); // 0
console.log(findLongestSubstring("rithmschool")); // 7
console.log(findLongestSubstring("thisisawesome")); // 6
console.log(findLongestSubstring("thecatinthehat")); // 7
console.log(findLongestSubstring("bbbbbb")); // 1
console.log(findLongestSubstring("longestsubstring")); // 8
console.log(findLongestSubstring("thisishowwedoit")); // 6

 

풀이

function findLongestSubstring(str) {
  let obj = {};
  let num = 0;
  let start = 0;
  // 중복위치 사이 찾기
  for (let i = 0; i < str.length; i++) {
    const index = obj[str[i]];
    if (index) {
      // 중복점 설정
      start = Math.max(start, index);
    }
    // 사이 갯수가 가장 많은거 찾기
    num = Math.max(num, i - start + 1);
    obj[str[i]] = i + 1;
  }
  return num;
}