[알자] 문제 해결 패턴 관련 문제 (1)

빈도수 세기

sameFrequencysameFrequency라는 함수를 작성하세요. 

두 개의 양의 정수가 주어졌을 때, 두 숫자의 자릿수가 같은 빈도를 갖는지 구합니다.

 

예시 

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

 

내가 작성한 코드

function sameFrequency(num1, num2) {
  const str1 = String(num1);
  const newArr1 = Array.from(str1);
  newArr1.sort((a, b) => a - b);

  const str2 = String(num2);
  const newArr2 = Array.from(str2);
  newArr2.sort((a, b) => a - b);

  if (newArr1.length !== newArr2.length) {
    return false;
  }

  for (let i = 0; i < newArr1.length; i++) {
    if (newArr1[i] !== newArr2[i]) {
      return false;
    }
  }

  return true;
}

 

접근 방식

1. 일단 숫자를 배열한다.

2. 배열로 만든 숫자를 오름차순 정렬한다.

3. for문/IndexOf를 통해 하나씩 비교해본다.

4. 반환할때 다시 숫자로 만든다.

1-4번까지가 처음 접근 방식이었다.

 

문제를 풀다보니 4번이 필요가 없고 그냥 true/false로 반환하면 된다.

배열에서 숫자를 정렬할때는 ((a-b)=>(a-b)로 정렬을 해야되는데 자꾸 까먹는다. 잊지말자

빈도수 세기/다중 포인터

문제

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

 

예시

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

 

내가 작성한 코드

function areThereDuplicates(...arr) {
  if (arr.every((item) => typeof item === 'number')) {
    arr.sort((a, b) => a - b);
  } else arr.sort();

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == arr[i + 1]) {
      return true;
    }
  }
  return false;
}

 

 

배열을 나열하기 위해 ... spread연산자를 작성했다.

areThereDuplicates(1, 2, 3) 같은 호출을 [1, 2, 3] 배열로 받아준다. 

function areThereDuplicates(arr) {
 arr = [...arr];
 arr.sort((a, b) => a - b);
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == arr[i + 1]) {
      return true;
    }
  }
  return false;
}

 

2번 줄처럼 작성하면 왜 안될까?

areThereDuplicates의 파라미터를 보자. arr로 인자를 받는다. 그러면 areThereDuplicates(1,2,3)으로 호출이된다. 

arr에는 1만 들어가고 나머지는 무시됨으로 파라미터값에 spread연산자를 작성해줘야된다. 

한마디로 파라미터에 (...arr)이런식으로 작성하면 자동 배열로 만들어준다. 중복 인자를 받고 싶을대는 ...arr로 함수 선언을 해야된다. 

 

Array.prototype.every()란?

배열의 모든 요소가 주어진 조건을 만족하는지 확인할 때 쓰는 메서드이다. 

arr.every(callbackFn)

callbackFn은 각 요소마다 실행되는 함수이다.

true만 계속 나오면 전체 결과도 true이고 중간에 false가 나오면 바로 false로 리턴한다 .

내가 작성한 코드 리펙토링

function areThereDuplicates(...arr) {
  let freq = {}; // 빈 객체 생성
  for (let item of arr) {
    freq[item] = (freq[item] || 0) + 1;
  }

  // 중복키를 센다.
  for (let key in freq) {
    if (freq[key] > 1) return true;
  }

  return false;
}

 

arr은 배열로 순회함으로 for...of를 작성했다.

freq는 객체를 순회함으로 for...in을 작성했다. 

 

다중포인터 

function areThereDuplicates(...args) {
  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;
}

빈도수 세기/다중 포인터

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

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 start = 0;
  let end = arr.length - 1;

  while (start < end) {
    if ((arr[start] + arr[end]) / 2 === avg) {
      return true;
    } else if ((arr[start] + arr[end]) / 2 < avg) {
      start++;
    } else {
      end--;
    }
  }

  return false;

 

처음에 접근했을때는 변수 명을 first랑 next로 지었다. 

0, 1

1, 2

이런식으로 증가하게 말이다. 

 

0과 1부터 시작하는 경우 → 연속된 쌍을 다룰 때 이용해야된다.

보통 정렬 여부가 상관 없다.

모든 인접 쌍을 이용할 때 사용해야 된다.

 

start = 0, end = arr.length - 1 → 정렬된 배열일 때 사용해야된다.

 

• 현재 문제처럼 정렬된 배열이 주어지고, 두 요소의 조합으로 뭔가 비교할 때 (합, 평균 등)
• 목표값보다 작으면 start를 올리고, 크면 end를 낮추는 식으로 효율적으로 탐색할 수 있다.

 

왜 start<end로 while문을 작성해야되는가? 

서로 다른 쌍을 찾기 위해서이다.

 

만약 start <= end로 하면?

마지막에 start === end가 되면서 자기 자신과 평균 비교가 된다.