[프로그래머스] 호텔 방 배정

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/64063

문제 풀이

• HashMap을 이용하여 풀이하였다.
• 가장 큰 문제는 방번호의 범위가 너무 크다는 점이다 (1조)
• 풀이는 다음과 같다.

  • HashMap에 (key, value)로 (들어간 방번호, 다음 들어갈 번호)를 저장한다.
  • 초기에는 (key, key+1)로 저장해준다.
  • 저장하다보면 다음과 같은 상황이 발생한다.
    1. 원하는 방에 대한 key가 이미 배정되어 있다.
    2. 원하는 방을 찾고 다음 들어갈 방 번호 (key+1)이 이미 배정되어 있다.
  • 위 상황을 해결하기 위해 배정가능한 방을 찾아가야 하고, 다음 들어갈 방 번호를 찾아가야 한다. (아래 while문 참조)
  • 추가로, 위 과정을 진행하기 위해 map을 순회해야하는데 순회하면서 이전에 들른 key들을 리스트에 저장해 놓고 다음 들어갈 방 번호가 정해지면 해당 값으로 업데이트시켜줘야 한다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        HashMap<Long, Long> map = new HashMap<>();
        long[] result = new long[room_number.length];
        int index = 0;
        for (int i = 0; i < room_number.length; i++) {
            long key = room_number[i];

            ArrayList<Long> tmp = new ArrayList<>();
            //key값 구하기
            while(true) {
                if (map.containsKey(key)) {
                    tmp.add(key);
                    key = map.get(key);
                } else {
                    break;
                }
            }

            //value값 구하기
            long value = key + 1;
            while(true) {
                if (map.containsKey(value)) {
                    tmp.add(key);
                    value = map.get(value);
                } else {
                    break;
                }
            }

            //이전 key들의 다음값 update
            for (long num : tmp) {
                map.put(num, value);
            }

            result[index++] = key;
            map.put(key, value);
        }
        return result;
    }
}