HashMap과 재귀 이용하기

프로그래머스 2019 카카오 인턴 Level 4 문제 호텔방 배정을 Java로 풀어보았다. 사실 내가 푼 건 아니다. 처음에는 HashSet을 이용해서 풀었는데 정확성 테스트만 통과하고 효율성 테스트는 다 틀렸다. 어떤 고민들을 했는지 살펴보자.

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/64063

---

HashSet이 아닌 HashMap

처음부터 HashMap을 떠올리지 못한 이유는 다음과 같다.
써 본 적이 없다. ㅎ

처음에는 HashSet에 만나게 되는 방 번호들을 추가해가며, contains() 메소드를 이용해서 이미 존재하는 방 번호라면 그 다음 번호를 구해줄 재귀 메소드를 선언해서 가장 가까운 큰 방 번호를 구해냈다. 하지만 결국 한 칸 한 칸 밀어가며 다 확인해야 하기 때문에 시간이 너무 오래 걸린다는 문제가 있었기에 효율성 테스트를 통과하지 못한 것 같다.

그렇다면 이미 존재하는 방 번호에 대해서 한 칸씩 다 밀어가며 찾을 것이 아니라 이미 그 다음 가능한 큰 방 번호를 함께 저장해준다면 훨씬 빠르게 빈 방을 찾아낼 수 있을 것이다. 이 원리를 HashMap과 재귀를 함께 이용해 구현해낼 수 있다.

static Long findEmptyRoom(long room_num) {
        if (!map.containsKey(room_num)) { // 빈 방이면 map에 다음 방 번호까지 함께 추가해주자
            map.put(room_num, room_num + 1);
            return room_num;
        }
        long empty = findEmptyRoom(map.get(room_num));
        map.put(room_num, empty);
        return empty;
    }

빈 방이면 바로 넣어주고, 빈 방이 아니면 재귀를 이용해서 빈 방을 찾아주고 재귀 시작점으로 돌아오며 앞서서 방문했던 비어 있지 않은 방에 대해서 다음 비어있는 방을 연결해주는 작업을 하는 것이다.

즉, 다음과 같은 구조로 HashMap을 채워나가는 것이다.

key: 선점된 방 -> value: 다음 빈 방

아래는 내가 제출한 전체 코드다.

import java.io.*;
import java.util.HashMap;

public class HotelRoom {
    static HashMap<Long, Long> map = new HashMap<>();

    static long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        for (int i = 0; i < room_number.length; i++)
            answer[i] = findEmptyRoom(room_number[i]);
        return answer;
    }

    static Long findEmptyRoom(long room_num) {
        if (!map.containsKey(room_num)) { // 빈 방이면 map에 다음 방 번호까지 함께 추가해주자
            map.put(room_num, room_num + 1);
            return room_num;
        }
        long empty = findEmptyRoom(map.get(room_num));
        map.put(room_num, empty);
        return empty;
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        long k = 10;
        long[] room_number = {1, 3, 4, 1, 3, 1};
        long[] result = solution(k, room_number);
        for (long num : result) bfw.write(num + " ");
        bfw.close();
    }
}

카카오 테크 블로그를 통한 정석적인 해설을 확인해볼 수 있다.
https://tech.kakao.com/2020/04/01/2019-internship-test/

오늘 배운 것

1. HashMap을 처음으로 사용해봤다.
2. 방 전체 개수가 10^12 개라서 배열로는 해결이 불가능했다. 그렇기 때문에 key값과 value값을 통한 Map을 이용해서 풀이를 해야한다는 생각을 떠올릴 수 있어야 한다.