[CodeKata] 프로그래머스(Lv3) : 숫자 게임

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

먼저, 지양했어야 하는 직관적인 풀이법이다. 물론 정확성 테스트는 통과했지만, 효율성에서 시간초과가 발생했다.

A를 순회하면서, B에 대한 findIndex(), splice() 가 각각 들어가면서 시간복잡도가 O(n) * 2사이클이 발생했기 때문일 것이다.

function solution(A, B) {
  let answer = 0;
  
  A = A.sort((a,b) => b-a)
  B = B.sort((a,b) => a-b)
  
  for (let num of A) {
    const idx = B.findIndex(n => n > num)
    if (idx !== -1) {
      B.splice(idx,1)
      answer++
    }
  }
  
  return answer
}

• answer은 정답을 누적할 변수다. 순회를 하면서 B의 숫자가 A의 숫자를 이기는 케이스가 발생하면 1씩 더한다.
• A는 내림차순, B는 오름차순으로 정렬한다. 추후 점수를 비교할 때, A는 큰값부터, B는 이를 이길 수 있는 가장 작은값부터 소모하는 것이 유리하기 때문이다.
• A를 순회하며, B에서 현재 A의 값(num)보다 큰 인덱스를 구한다. 이것이 존재한다면, answer에 1을 더하고 B에선 splice() 해준다.

 

시간초과를 줄일수 있는 방법에 대해 고민해보았다. 위의 내 풀이는 A를 순회하면서, 매번 B를 인덱스 순회, 삭제 순회를 진행했다.

이를, 한 번의 순회에서 모두 처리할 수 있는 방법을 고민했다.

function solution(A, B) {
  let answer = 0;
  A = A.sort((a,b) => b-a)
  B = B.sort((a,b) => b-a)
  
  let j = 0;
  for (let i = 0 ; i < A.length ; i++) {
    if (A[i] < B[j]) {
      answer++;
      j++
    }
  }
  
  return answer
}

• A, B를 내림차순으로 정렬했다. A의 가장 큰 값부터 이길 수 있는 B의 값을 찾기 위해서이다.
• i는 A를 순회하는 인덱스, j는 B에 대한 인덱스이다. A를 순회하며 비교하는데, A의 현재값보다 B가 크다면 현재 케이스로 B팀은 1승을 할 수 있다. answer에 1을 더해주고, B의 현재값을 소모했기에 인덱스(j) 역시 1을 더한다.
• A의 현재값이 더 크거나 같다면 현재 B값을 소모할 필요가 없다. 이 땐 if문을 거치지 않으므로, B의 인덱스는 유지되고 A만 다음 인덱스로 이동하여 비교를 진행한다.

 

🖇 리뷰

간만에 내 스스로 풀었으며, 이보다 나은 모범답안을 찾지 못한 문제이다! (매우 뿌듯 😁😁😁)

다른 레벨3 문제에 비하면 쉬운 편이긴 했으나, 무엇보다 문제에 나온 풀이경과를 그대로 구현하려고 하면 안됨을 다시금 느낀 계기였다.