2023.02.03

📖오늘 배운  것

문제 해결 패턴

빈도수 세기 패턴(FREQUENCY COUNTERS)

: 자바스크립트의 객체를 사용해서 다양한 값과 빈도를 수집

 

예시) same 함수에게 2개의 배열을 전달하고, 두번째 배열의 값들이 첫 번재 배열의 제곱에 해당하는 값을 가지면 true를 반환.

same([1, 2, 3], [4, 1, 9]) //true
same([1, 2, 3], [1, 9])//false
same([1, 2, 1], [4, 4, 1]) //false

 

• 중첩루프를 사용하는 경우

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^2)인데 그 이유는 indexOf는 하나의 반복문을 단축해서 표현한 것이기 때문에 결과적으로 중첩루프를 사용한 것과 시간복잡도가 같다.

 

• 빈도수 세기 패턴

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;
  }
  
  for(let key in frequencyCounter1) {
    if(!(key **2 in frequencyCounter2)) return false;
    if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]) return false;
  }
  
  return true;
}

위의 코드는 빈도수 세기 패턴, 즉 객체를 활용한 코드이다. 중첩루프가 없어진 대신 여러 개의 반복문이 사용되었는데 두 개의 반복문이 중접된 개별 루프보다 훨씬 낫다! 개별 루프가 2개인 경우 만약 n이 1000이라면 2000번을 돌면되는데 중첩 루프인 경우 1000 * 1000 만큼 돌아야하기 때문이다. 따라서 웬만하면 중첩 루프는 지양하는 것이 좋다.

 

위의 코드처럼 입력값에 대해 존재여부뿐만 아니라 빈도수도 일치해야하는 경우 객체를 활용해서 값을 비교하는 방법을 사용하면 편리하다.

 

문제) 두 개의 문자열을 함수에 전달했을 때 두 문자열이 모두 일치하는 글자를 가지는지 확인

function validAnagram(string1, string2){
  if(string1.length !== string2.length) return false;
  
  const stringObj = {};
  for(let str of string1) {
    stringObj[str] = (stringObj[str] || 0) + 1;
  }

  for(let str of string2) {
    if(!stringObj[str]) return false;
      --stringObj[str];
  }
  
  return true;
}

두 개의 문자열이 길이가 다른 경우 조건을 만족할 수 없으므로 바로 false를 리턴한다.

첫번째 문자열을 반복문을 돌면서 객체에 글자 개수를 저장한다. 

그리고 두번째 문자열을 반복문으로 돌면서 해당 값이 위에서 저장한 객체에 존재하면 -1을 해준다.

 

 

다중 포인터(MULTIPLE POINTERS)

:인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것

 

예시) 오름차순으로 정렬된 배열을 취하는 sumZero 라는 함수를 작성한다. 이 배열에서 한 쌍의 합이 0이 되는 경우가 있다면 첫번째 쌍을 배열로 리턴한다. 없는 경우 undefined를 리턴한다.

❗중요한 점은 배열이 정렬된 상태라는 것이다❗

• 중첩루프를 사용하는 경우

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[1], arr[j]];
      }
    }
  }
}

시간 복잡도: O(n^2)

공간 복잡도: 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++;
    }
  }
}

시간 복잡도: O(n)

공간 복잡도: O(1)

 

 

문제) countUniqueValues라는 함수를 구현하여 정렬된 배열을 전달하면 해당 배열의 중복을 제외한 고유한 값의 개수를 반환하도록 한다.

function countUniqueValues(arr){
  let i = 0;
  let j = 1;
  
  while(j <= arr.length - 1) {
    if(arr[i] !== arr[j]){
      i++;
      arr[i] = arr[j];
    }
    j++;
  }
  
return arr.length > 0 ? i+1 : i;
}

포인터를 같은 방향으로 진행시키도록 한다. i = 0, j= 1에서 시작하면서 만약 i와 j가 같은 경우 중복된 값이기 때문에 i는 그대로 두고 j를 +1 한다. 만약 다르다면 i에 +1을 한 후 현재 인덱스 i의 값을 j의 값으로 변경한다. 즉, 고유의 값을 배열의 앞에 정렬하도록 하는 것이다.

 

다중 포인터 부분이라 해당 패턴을 활용해서 문제를 풀었는데 다른 방법으로 Set을 이용하면 쉽게 중복을 해결할 수 있을 것 같다.

 

 

 

 

💭배운 점

점점 알고리즘 개념 자체에 다가가고 있는 것 같다. 아직까지 들어본 부분도 있고 예시 코드나 문제가 쉬운 편이라 이해하는데에 어려움은 없지만 본격적인 알고리즘을 배우게 되면 어려울 거라는 걱정이 든다. 하지만 이렇게 문제 해결패턴 등을 먼저 배우고 알고리즘을 배우는 것이기 때문에 어떤 상황에서 어떤 패턴을 써야하고, 어떤 알고리즘은 어떻게 풀어야하는지 차근차근 배우는 기분이 들어서 좋다. 욕심내서 진도를 빼는 것보다 이해에 중점을 둬서 중간에 탈주하지 않고 완강하는 것을 목표로 잡아야겠다.