[프로그래머스 lev3/JS] 숫자 게임

문제 출처

프로그래머스 lev3 - 숫자 게임

나의 풀이

1차시도 (정확성 통과, 효율성 실패)

const solution = (ta, tb) => {
  ta.sort((a,b) => a-b)
  tb.sort((a,b) => a-b)

  // console.log(ta, tb)
  let answer = 0
  for(let i=0; i<tb.length; i++){
    if(tb[i] > ta[0]){
      answer++ 
      ta.shift()
    }
  }
  return answer
}

console.log(solution([5, 1, 3, 7], [2, 2, 6, 8])) // 3
// console.log(solution([2, 2, 2, 2], [1, 1, 1, 1])) // 0

2차시도 (통과)

크기가 커서 완전탐색은 불가능할 것 같았다.
그리디 느낌이 강하게 들었다. 그리디는 정렬 개념을 자주 필요로 한다.

array.shift()가 시간복잡도를 잡아먹는 것 같으므로
answer를 index 삼아서 계산했더니 효율성을 통과했다.

첫번째 tc의 team B 숫자 배열(tb) [2, 2, 6, 8]을 보면
tb[0], tb[1]은 이길 수 있는 숫자가 1개이다
tb[2]는 이길 수 있는 숫자가 3개이다
tb[3]은 이길 수 있는 숫자가 4개이다.

값이 크면 클 수록 위치의 자유도를 받는다(어디에 위치되어도 이길 수 있다).
반면 값이 작으면 작을 수록 들어갈 수 있는 위치가 한정되어 있다.

예를 들어 tb[3]인 8은 가장 뒤에 배치되어도 이길 수 있다.
반면 tb[0]은 가장 앞에 위치해야만 이길 수 있다.

그러므로 오름차순으로 정렬을 진행한 뒤,
순서대로 이겼을 때 배열 ta의 index를 증가시켜주는 식으로 진행하면 가장 많이 이길 수 있는 경우의 수를 구할 수 있다.

const solution = (ta, tb) => {
  ta.sort((a,b) => a-b)
  tb.sort((a,b) => a-b)

  // console.log(ta, tb)
  let answer = 0
  for(let i=0; i<tb.length; i++){
    if(tb[i] > ta[answer]){
      answer++ 
    }
  }
  return answer
}

다른 풀이

function solution(A,B){
  var point = 0;
  A = A.sort(function(a,b){return a-b});
  B = B.sort(function(a,b){return a-b});

  var temp=0;
  for(var i=0;i<A.length; i++){
    for(var j=temp;j<B.length;j++){       
      // console.log("a-"+i+"/b"+j);
      if(A[i]<B[j]){
        point++;
        //B.splice(j,1);
        temp=j+1;
        break;
      }

  }

  }
  return point;
}