프로그래머스-호텔 방 배정

문제 요약

• 10^12 크기의 K와 1차원 배열의 숫자 입력이 주어질 때 조건에 맞는 정답을 1차원 배열에 순차적으로 나타내라.

첫번째 접근

• 네번째 조건이 눈길이 끌었다.

  고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

• Upper_Bound가 바로 떠올랐고 HashSet을 이용하여 방문처리를 하였다.

• 핵심은 이미 방문한 방이 주어질때만 Upper_Bound를 수행하는 것.

결과

• 20% 정답율

두번째 접근

• Linked List를 1차원 배열로 만들어 조회할 수 있도록 구성한다.

  next[1] = 2, next[2] = 3, next[3] = 4,
  2를 방문한다면 next[2] = next[3] (next[2] = 4)
  이후에 2를 재방문하게 되면 4를 조회할 수 있다.

결과

• K의 크기만큼 공간 효율을 낼 수 없어서 불가능한 구상이었다.

세번째 접근

• 그러면 Map을 활용하자.

  Map<Long, Long>을 통해 containsKey가 없다면 Map.put(roomId, roomId + 1)하고 roomId를 저장
  있다면 next = find(Map.get(roomId)) 수행하고 next를 저장

결과

• 정답율 100%

후기

• 서로소 집합에 대한 문제였다. Union-Find를 사용하기 좋은 문제였지만 10^12에 이분탐색부터 생각하고 말았다. 앞으로는 여러 알고리즘을 구상하고 시뮬레이션을 해서 정답에 접근할 것이다.