(이코테) 모험가 길드 문제 풀이

처음에 볼때는 쉬웠는데, 풀수록 어려워져서 글로 남기기로 했다.

문제

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다.

N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.

예시

values = [1, 2, 2, 2, 3]
answer = 2

values = [2, 3, 3, 3, 3, 4]
answer = 1

Solution 1

Intuition

예를 들어 공포도가 9인 사람이 있다고 하자. 그럼 그 사람이 모험을 떠나기 위해서는 9명의 그룹을 만들어야한다.

그렇다면 공포도가 가장 큰 사람을 기준으로 그룹을 만들어서 보내고, 남는 사람들 중에서 똑같이 공포도가 (가장) 큰 사람을 기준으로 그룹을 만들면 되지 않을까?

하지만 그러면 공포도가 큰 사람이 행복한 것이지 그룹 수가 최대값이 되지는 않는다. 공포도가 적은 사람부터 먼저 그룹을 만들어서 보내야 그룹 수가 최대가 된다.

Approach

따라서 오름차순으로 정렬하고 공포도가 낮은 사람부터 최대한 적은 인원으로 그룹을 지어서 보내야한다.

index  0 1 2 3 4
value  1 2 2 2 3
group  ─ ──
answer: 2

index  0 1 2 3 4 5
value  2 3 3 3 3 4
group  ───
answer = 1

Complexity

오름차순 정렬: O(n log n)

그룹 짓기: O(n)

최종 시간 복잡도: O(n log n)

Solution 2

Intuition

그런데 그룹 짓기 과정이 뭔가 Naive한 느낌이다.

index  0 1 2 3 4
value  1 1 1 1 1
group  ─ ─ ─ ─ ─

현재 인덱스 0을 보고 있다고 하자. 그렇다면 값이 1인 모험가 수만 세면 새로 생기는 그룹은 count / 1개로 계산할 수 있다.

이 방법은 그룹 크기가 1인 경우만 가능한가?

index  0 1 2 3 4
value  2 2 2 2 2
group  ─── ───

이 경우 그룹 크기는 2이므로, 2의 개수를 전부 세면 count / 2로 계산할 수 있다. 따라서 이 방법은 공포도 값에 관계없이 모두 적용 가능하다.

Approach

그러면 현재 공포도 값이 같은 모험가를 세는 방법을 어떻게 빠르게 할 수 있을까?

현재 세야 하는 공포도가 size일 때, 어차피 정렬은 되어있으니까 이진 탐색 size+1을 하면 된다.

더 복잡한 것 처럼 보일 수 있지만, 막상 구현하니까 더 간결했다. 왜냐하면 대부분 이진탐색 구현 함수는 찾는 값이 없을 때 인덱스 n(array 크기)을 반환하기 때문이다.

나의 구현 코드의 메인 루프를 보면 3줄밖에 없다.

function solve(nums: number[]) {
  nums = nums.sort((a, b) => a - b)
  const n = nums.length
  let index = 0
  let groups = 0
  let size = nums[0]

  // Loop!
  while (true) {
    const boundary = increaseSafely(size)

    if (boundary === n) break

    size = nums[boundary]
  }

  ...

  return groups
}

클로저 함수 increaseSafely()도 뜯어보면 복잡한 인덱스 처리가 없다. search()함수 구현은 여기에 있다.

function increaseSafely(size: number): number {
  // find index of size+1
  const boundary = search(n, x => size + 1 <= nums[x], index)

  // calculate members
  const membersWithSameSize = boundary - index

  // calculate groups
  const increaseGroup = Math.floor(membersWithSameSize / size)
  groups += increaseGroup
  index += increaseGroup * size

  return boundary
}

Solution

function solve(nums: number[]) {
  nums = nums.sort((a, b) => a - b)
  const n = nums.length
  let index = 0
  let groups = 0
  let size = nums[0]

  while (true) {
    const boundary = increaseSafely(size)

    if (boundary === n) break

    size = nums[boundary]
  }

  /**
   * Increases index and group safely
   */
  function increaseSafely(size: number): number {
    const boundary = search(n, x => size + 1 <= nums[x], index)
    const membersWithSameSize = boundary - index

    // increase group
    const increaseGroup = Math.floor(membersWithSameSize / size)
    groups += increaseGroup
    index += increaseGroup * size

    return boundary
  }

  return groups
}

function search(n: number, f: (x: number) => boolean, i = 0) {
  let j = n

  while (i < j) {
    const h = (i+j) >> 1
    if (!f(h)) {
      i = h + 1
    } else {
      j = h
    }
  }

  return i
}

Complexity

그룹 짓기 시간 복잡도의 수식 O(v log n) 은 좋지 않아 보인다.

최악의 경우 v == n이므로 더 느리지만 대부분의 경우 v <<< n이다.

따라서 Solution 2가 더 빠르다고 볼 수 있다.