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

문제

A팀과 B팀이 각각 N명으로 숫자 게임을 한다. A팀 순서는 고정, B팀은 순서를 조정해 최대 승점을 얻어야 한다.

1단계: 정확성 우선

function solution(A, B) {
  B.sort((x, y) => x - y);

  let score = 0;
  let used = new Array(B.length).fill(false);

  for (let i = 0; i < A.length; i++) {
    for (let j = 0; j < B.length; j++) {
      if (!used[j] && B[j] > A[i]) {
        score++;
        used[j] = true;
        break;
      }
    }
  }

  return score;
}

• B를 오름차순 정렬
• A[i]보다 큰 B 중 가장 작은 값 선택
• used로 사용 여부 관리

시간복잡도: O(n²)
결과: 정확성 통과, 효율성 실패

2단계: 잘못된 최적화

// 이렇게 하면 안됨
function solution(A, B) {
  B.sort((x, y) => x - y);

  let score = 0;
  let bIndex = 0;

  for (let i = 0; i < A.length; i++) {
    while (bIndex < B.length && B[bIndex] <= A[i]) {
      bIndex++;
    }

    if (bIndex < B.length) {
      score++;
      bIndex++;
    }
  }

  return score;
}

• bIndex를 단순 증가시키면 사용한 카드를 재사용할 수 있음
• 결과가 달라짐

3단계: 이진 탐색 + 순차 탐색

function solution(A, B) {
  B.sort((x, y) => x - y);

  let score = 0;
  let used = new Array(B.length).fill(false);

  for (let i = 0; i < A.length; i++) {
    // 이진탐색으로 시작점 찾기
    let left = 0, right = B.length - 1;
    let start = B.length;

    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (B[mid] > A[i]) {
        start = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    // 그 지점부터 순차탐색
    for (let j = start; j < B.length; j++) {
      if (!used[j]) {
        score++;
        used[j] = true;
        break;
      }
    }
  }

  return score;
}

• 이진 탐색으로 시작점을 O(log n)에 결정
• 필요한 구간만 순차 탐색
• 정확성 유지

시간복잡도: 평균 O(n log n), 최악 O(n²)
결과: 정확성 + 효율성 통과

요약

• 정확성 우선, 효율성은 그 다음
• 이진 탐색으로 범위를 줄이고, 필요한 부분만 순차 탐색
• 이론적 최적보다 실용적 최적을 선택

성능 비교

단계	시간복잡도	효율성 테스트
1단계	O(n²)	실패
2단계	O(n log n)	결과 오류
3단계	O(n log n)	통과

마무리

정확성 → 효율성 순서로 접근하고, 이진 탐색과 순차 탐색을 조합해 효율성 테스트를 통과했다.