[JS] 프로그래머스_Level 3_숫자 게임

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12987

프로그래머스

 

풀이

해당 문제는 주어진 숫자 배열에 대응하는 새로운 숫자 배열을 만들어 숫자들의 크기 비교후 대응하는 숫자들의 크기 비교를 하여 큰 숫자 들의 수를 최대로 만드는 문제이다.

 

A와 B 숫자 배열이 주어지는데, A 숫자 배열의 숫자들 보다 큰 숫자들의 개수의 최대값을 구하면 되는 문제다.

 

이때 A 배열은 고정되어 있으며 B 배열만 순서를 바꿀 수 있다. 이는 A 배열에 있는 숫자들의 대응하는 숫자를 마음대로 할 수 있음을 알 수 있다. 

 

그렇다면 크기 비교를 위해 sort 메서드를 이용해 두 배열을 정렬해주면 원활하게 크기 비교가 가능해진다.

 

그렇다면 크기비교를 구현해야 하는데, 어떻게 진행해야할까? 그리디를 이용해 각 숫자를 비교하고 중복으로 사용이 불가능하니 shift나 splice와 같이 직접 배열을 조작해주면 시간 복잡도면에서 불리하니 투포인터 알고리즘을 이용해 비교를 하기로 했다.

 

투포인터 알고리즘을 이용해 크기 비교후 B의 숫자가 더 크다면 answer++ 동작을 해주고, 한번 사용한 숫자는 다시 사용할 수 없으므로 비교를 시작하는 위치를 나타내는 lp와 현재 비교한 rp를 1씩 증가해준다. 그리고 B 숫자가 A숫자보다 작거나 같은 경우는 rp만 증가시켜 다음 숫자를 비교하도록 한다.

 

 

코드

function solution(A, B) {
  let lp = 0;
  let rp = 0;
  let answer = 0;
    
  A = A.sort((a, b) => a - b);
  B = B.sort((a, b) => a - b);
    
  while (lp < B.length) {
    if (B[lp] > A[rp]) {
      answer++;
      lp++;
      rp++;
    }
    else {
      lp++
    }
  }
    
  return answer;
}