JS Coding Blog

요청한 번호 이상에서 가장 이른 빈 좌석 배정하기

자바스크립트 코딩테스트 문제로 disjoint-set-successor 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium disjoint-set-successor 함수명: assignEarliestAvailableSeat 제한 시간: 300ms

각 요청마다 요청한 번호 이상이면서 아직 비어 있는 좌석 중 가장 작은 번호를 빠르게 찾아 배정하는 문제입니다.

문제 설명

공연장에 1번부터 maxSeat번까지의 좌석이 있습니다.

좌석 요청 배열 requests의 각 원소는 한 사람이 최소한 이 번호 이상의 좌석을 원한다는 뜻입니다. 각 요청을 순서대로 처리하면서,

  • 아직 비어 있는 좌석 중
  • 요청한 번호 이상인 좌석만 후보로 보고
  • 그중 가장 번호가 작은 좌석을 배정합니다.

조건을 만족하는 좌석이 더 이상 없으면 -1을 배정합니다.

각 요청에 대해 실제로 배정된 좌석 번호를 배열로 반환하는 assignEarliestAvailableSeat 함수를 작성하세요.

예를 들어 maxSeat = 5, requests = [2, 1, 1, 4, 3]이면

  1. 2 요청 → 2 배정
  2. 1 요청 → 1 배정
  3. 1 요청 → 3 배정
  4. 4 요청 → 4 배정
  5. 3 요청 → 5 배정

따라서 결과는 [2, 1, 3, 4, 5]입니다.

제한사항

  • 1 <= maxSeat <= 200000
  • 1 <= requests.length <= 200000
  • 1 <= requests[i] <= maxSeat
  • 각 요청은 순서대로 처리해야 합니다.
  • 한 번 배정된 좌석은 다시 사용할 수 없습니다.
  • 가능한 한 전체를 O((maxSeat + requests.length) * α(n)) 또는 그에 가까운 수준으로 해결해 보세요.

예시

  • 입력: maxSeat = 5, requests = [2, 1, 1, 4, 3] → 출력: [2, 1, 3, 4, 5]
  • 입력: maxSeat = 4, requests = [3, 3, 3, 3, 3] → 출력: [3, 4, -1, -1, -1]
  • 입력: maxSeat = 6, requests = [5, 2, 6, 2, 4] → 출력: [5, 2, 6, 3, 4]

두 번째 예시에서는 3, 4를 쓴 뒤에는 3 이상인 빈 좌석이 없으므로 나머지는 모두 -1입니다.

힌트

  • 요청마다 오른쪽으로 한 칸씩 선형 탐색하면 최악의 경우 너무 느립니다.
  • 어떤 좌석이 이미 사용됐다면, 그 좌석 다음에 확인해야 할 다음 후보 좌석을 바로 가리키게 만들 수 있습니다.
  • Disjoint Set Union(Union-Find)을 연결성 판별이 아니라 다음 사용 가능한 번호 찾기 용도로도 활용할 수 있습니다.

해설

이 문제를 단순하게 풀면 각 요청마다 requests[i]부터 오른쪽으로 비어 있는 좌석을 찾을 때까지 검사해야 합니다.

예를 들어 요청이 계속 [1, 1, 1, 1, ...]처럼 들어오면 이미 찬 좌석을 반복해서 다시 보게 되어 최악의 경우 O(n^2)까지 커질 수 있습니다.

핵심은 이미 사용한 좌석은 다음 후보로 건너뛴다는 것입니다.

1. parent[x]의 의미

Union-Find의 parent[x]를 보통 같은 집합의 대표로 쓰지만, 이 문제에서는 조금 다르게 해석할 수 있습니다.

find(x)를 호출했을 때 x 이상에서 아직 비어 있는 가장 작은 좌석 번호를 돌려주도록 만들 수 있습니다.

이를 위해 좌석 x를 사용한 직후에는 x의 다음 후보를 x + 1 쪽으로 넘깁니다.

즉 좌석 x를 배정했다면

  • 이제 x는 더 이상 비어 있지 않으므로
  • 다음에 x를 찾으러 오면 x + 1부터 보게 만들어야 합니다.

그래서 배정 직후 parent[x] = find(x + 1) 처럼 연결합니다.

2. sentry 역할의 maxSeat + 1

마지막 좌석까지 다 찬 경우도 처리해야 하므로 maxSeat + 1을 더 이상 배정 가능한 좌석이 없음을 뜻하는 특별한 번호로 둡니다.

  • find(maxSeat + 1) = maxSeat + 1
  • 어떤 요청에서 find(request) 결과가 maxSeat + 1이면 정답은 -1

이 sentry 덕분에 범위 밖 예외 처리가 깔끔해집니다.

3. 요청 처리 흐름

각 요청 r에 대해:

  1. seat = find(r)
  2. seat === maxSeat + 1 이면 -1 추가
  3. 아니면 그 좌석을 배정하고 결과에 seat 추가
  4. 이후 parent[seat] = find(seat + 1)로 갱신

이렇게 하면 다음에 같은 좌석이나 그보다 왼쪽에서 다시 찾아도 이미 찬 좌석들을 한 번에 건너뜁니다.

4. 왜 path compression이 중요한가?

예를 들어 1, 1, 1, 1, 1 요청이 반복되면 처음에는 1 -> 2 -> 3 -> 4 ... 식으로 이어질 수 있습니다.

하지만 find를 할 때마다 경로 압축을 적용하면 중간 노드들이 곧바로 가장 가까운 다음 빈 좌석을 가리키게 됩니다.

그래서 이미 사용한 좌석들을 매번 길게 다시 따라가지 않고, 거의 상수 시간에 가까운 속도로 다음 빈 좌석을 찾을 수 있습니다.

5. 예시 추적

maxSeat = 5, requests = [2, 1, 1, 4, 3]

초기에는 각 좌석이 자기 자신을 가리킵니다.

  • 요청 2 → find(2) = 2 → 2 배정 → parent[2] = find(3)
  • 요청 1 → find(1) = 1 → 1 배정 → parent[1] = find(2)인데 이제 2는 이미 사용됐으므로 결국 3으로 압축
  • 요청 1 → find(1) = 3 → 3 배정
  • 요청 4 → find(4) = 4 → 4 배정
  • 요청 3 → find(3) = 5 → 5 배정

결과는 [2, 1, 3, 4, 5]가 됩니다.

6. 복잡도

  • 초기화: O(maxSeat)
  • 각 요청 처리: 경로 압축이 있는 Union-Find 기준 거의 상수 시간
  • 전체: O((maxSeat + requests.length) * α(n))

여기서 α(n)은 아커만 역함수로, 실전에서는 거의 상수처럼 생각해도 됩니다.

이 문제로 익혀 둘 포인트는 Union-Find가 연결 요소 판별뿐 아니라, 다음 사용 가능한 값 찾기(successor query) 같은 문제에도 매우 강력하다는 점입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.