문제 해결 패턴 연습 문제

문제 1

sameFrequency 라는 함수를 작성하세요. 두 개의 양의 정수가 주어졌을 때, 두 숫자의 자릿수가 같은 빈도를 갖는지 구합니다.

 

여러분의 솔루션은 반드시 다음과 같은 복잡성을 가져야 합니다.

 

Time: O(N)

 

예시

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

 

 

정답

function sameFrequency(num1, num2) {
  // 빈도수를 담아둘 객체
  const frequency1 = {};
  const frequency2 = {};

  // string화
  const str1 = num1.toString();
  const str2 = num2.toString();

  const str1Length = str1.length;
  const str2Length = str2.length;

  // 길이가 같지 않다면 빈도수가 다름
  if (str1Length !== str2Length) {
    return false;
  }

  // 각 문자별로 객체에 빈도수를 저장
  for (let i = 0; i < str1Length; i++) {
    const s = str1[i];
    frequency1[s] = (frequency1[s] || 0) + 1;
  }
  for (let i = 0; i < str2Length; i++) {
    const s = str2[i];
    frequency2[s] = (frequency2[s] || 0) + 1;
  }

  for (let t in frequency1) {
    if (frequency2[t] !== frequency1[t]) {
      return false;
    }
  }

  return true;
}

 

 

문제 2

가변적인 수의 인수(a variable number of arguments)를 받아들이고 전달된 인자 중 중복이 있는지 확인하는 areThereDuplicates라는 함수를 구현합니다.  빈도 카운터 패턴 또는 다중 포인터 패턴을 사용하여 이 문제를 해결할 수 있습니다.

 

Time - O(n)

Space - O(n)

 

예시

areThereDuplicates(1, 2, 3); // false
areThereDuplicates(1, 2, 2); // true
areThereDuplicates('a', 'b', 'c', 'a'); // true

 

정답

function areThereDuplicates(...arr) {
  // 갯수를 담아둘 객체를 생성
  const obj = {};

  // 반복문을 돌면서 하나씩 저장
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    // 이미 객체가 있는 경우 return ture
    if (obj[current]) {
      return true;
    }
    obj[current] = (obj[current] || 0) + 1;
  }
  // 마지막에 도달한 경우 return false
  return false;
}

 

문제 3

averagePair라는 함수를 작성합니다. 정렬된 정수 배열과 목표 평균이 주어졌을 때, 배열에 쌍의 평균이 목표 평균과 같은 값의 쌍이 있는지 확인합니다. 목표 평균과 일치하는 쌍이 두 개 이상 있을 수 있습니다.

 

Time: O(N)

Space: O(1)

 

예시

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) {
  //   양쪽에 포인터를 하나씩 둠
  let left = 0;
  let right = arr.length - 1;
  //   평균의 값을 2배 한 값을 구함.
  const avg2 = avg * 2;
  // 포인터 왼쪽이 작아질때까지 반복문을 돔.
  while (left < right) {
    // 양 포인터의 값을 합함.
    const sum = arr[left] + arr[right];
    // 합이 같은 경우 정답
    if (sum === avg2) {
      return true;
    } else if (sum < avg2) {
      // 만약 포인터의 값을 합한게 2배 값보다 작다면 왼쪽 포인터를 늘림.
      left++;
    } else {
      // 만약 포인터의 값을 합한게 2배 값보다 크다면 오른쪽 포인터를 줄임.
      right--;
    }
  }
  // 전부 반복했는데 정답이 없는 경우
  return false;
}

 

문제 4

두 문자열을 받아 첫 번째 문자열의 문자가 두 번째 문자열의 문자의 일부에 포함되는지 확인하는 isSubsequence라는 함수를 작성합니다. 즉, 이 함수는 첫 번째 문자열의 문자가 순서가 바뀌지 않고 두 번째 문자열의 어딘가에 나타나는지 확인해야 합니다.

 

Time: O(N + M)

Space: O(1)

예시

isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)

 

 

정답

function isSubsequence(str1, str2) {
  let i = 0;
  let 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;
}

 

 

문제 5

정수의 배열과 숫자가 주어졌을 때, 함수에 전달된 숫자의 길이를 가진 하위 배열의 최대 합을 구하는 maxSubarraySum이라는 함수를 작성하세요.

 

하위 배열은 원래 배열의 연속적인 요소로 구성되어야 한다는 점에 유의하세요. 아래 첫 번째 예제에서 [100, 200, 300]은 원래 배열의 하위 배열이지만 [100, 300]은 그렇지 않습니다.

 

Time: O(N)

Space: O(1)

 

예시

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

 

정답

function maxSubarraySum(arr, num) {
  // 최대 합 선언
  let maxSum = 0;
  // 임시 합
  let tempSum = 0;
  // num보다 arr의 길이가 작으면  null return
  if (arr.length < num) {
    return null;
  }

  // 첫번째 임시 합을 구함
  for (let i = 0; i < num; i++) {
    tempSum += arr[i];
  }

  // 현재 최대 합은 첫번째 합
  maxSum = tempSum;

  for (let i = num; i < arr.length; i++) {
    // 반복문을 돌며 앞에 숫자를 빼고 뒤에 숫자를 더함.
    tempSum = tempSum - arr[i - num] + arr[i];
    // 둘 중 더 큰 값이 maxSum
    maxSum = Math.max(maxSum, tempSum);
  }

  return maxSum;
}

 

문제 6

 

양수 배열과 양수라는 두 개의 매개 변수를 받아들이는 minSubArrayLen이라는 함수를 작성하세요.

이 함수는 합이 함수에 전달된 정수보다 크거나 같은 인접한 하위 배열의 최소 길이를 반환해야 합니다. 값이 없는 경우 0을 반환합니다.

 

Time: O(n)

Space: O(1)

예시

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

 

정답

const minSubArrayLen = (nums, sum) => {
  // 전체값, 시작 인덱스 끝 인덱스, 최소 길이 변수 초기화
  let total = 0;
  let start = 0;
  let end = 0;
  let minLen = Infinity;

  // start가 배열의 길이보다 작은 동안 루프를 반복
  while (start < nums.length) {
    // 현재 윈도우의 합이 sum보다 작고 end가 배열의 끝에 도달하지 않은 경우
    // end를 증가시키면서 윈도우를 확장하고 total에 nums[end] 값을 더함
    if (total < sum && end < nums.length) {
      total += nums[end];
      end++;
    } else if (total >= sum) {
      // 현재 윈도우의 합이 sum보다 크거나 같은 경우, 최소 길이를 계산하여 minLen을 업데이트한다.
      // 그런 다음, start를 증가시키면서 윈도우를 축소하고 total에서 nums[start] 값을 뺀다.
      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;
};

 

 

문제 7

문자열을 받아 모든 고유 문자가 포함된 가장 긴 하위 문자열의 길이를 반환하는 findLongestSubstring이라는 함수를 작성하세요.

 

Time: O(n)

 

예시

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring('longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

 

정답

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]) {
      start = Math.max(start, seen[char]);
    }
    longest = Math.max(longest, i - start + 1);
    seen[char] = i + 1;
  }
  return longest;
}