230126 Climbing the Leaderboard

매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅

HakerRank 문제!
문제가 영어로 제시되니 조금이라도 헷갈리는 부분이 생기면 이해하거나 인지하는 데 더 오랜 시간이 걸리는 것 같다.
그래도 주 5회 중에 3번 정도는 영어로 풀어야겠다는 생각이 든다.
그래야 앞으로 풀게 될 코딩테스트에서도 난감한 상황이 벌어지지 않을듯.

문제 링크

Climbing the Leaderboard

해설

1. 시간 초과 코드
모든 경우의 수를 탐색하는 것이기 때문에 테스트케이스가 엄청나게 늘어날 경우 결국 시간초과로 통과되지 않는다.
4개 정도의 테스트 케이스에서 막혔던 것으로 기억.

function climbingLeaderboard(ranked, player) {
  const resultArray = [];
  const removeDuplicateItemWithRanked = [...new Set(ranked)];

  for (let i = 0; i < player.length; i += 1) {
    const rankedWithPlayer = [...removeDuplicateItemWithRanked, player[i]].sort((a, b) => b - a);

    const rankOfPlayer = rankedWithPlayer.findIndex((value) => value === player[i]) + 1;

    resultArray.push(rankOfPlayer);
  }

  return resultArray;
}

2. 멀쩡한 코드(ㅎㅎ)
계속 해결되지 않아 다른 사람들의 해설을 참고하여 확인해보니 이진검색 방법을 통해 시간 초과 문제를 해결 가능하다고 확인했다.

참고한 블로그 링크를 함께 첨부한다.

function lowerBound(array, target) {
  let left = 0;
  let right = array.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (array[mid] <= target) {
      right = mid;
      continue;
    }

    left = mid + 1;
  }

  return left;
}

function climbingLeaderboard(ranked, player) {
  const resultArray = [];
  const removeDuplicateItemWithRanked = [...new Set(ranked)];

  for (let i = 0; i < player.length; i += 1) {
    resultArray.push(lowerBound(removeDuplicateItemWithRanked, player[i]) + 1);
  }

  return resultArray;
}

이진 탐색을 쉽게 설명한 유튜브 영상을 봤는데, 사실 내용은 뭔지 알겠고. 중요한건 어떻게 코드로 구현할 것이냐인 것 같다.

오늘 봤던 다른 코테에서도 시간 초과 때문에 정말 고통만 받다가 끝났는데...
빨리 코딩 테스트 능력을 키워서 이 절망감에서 벗어나고 싶다.