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

카테고리

재귀

나만의 카테고리

재귀, 효율적 풀이

문제 링크

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

코딩테스트 연습 - 호텔 방 배정

요점

• 같은 로직을 효율적인 방법으로 풀이하는 방법을 알아야한다.

참고 지식

• 재귀

풀이 (Java)

import java.util.*;

class Solution {
    Map<Long, Long> roomMap = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        int roomLength = room_number.length;
        long[] rooms = new long[roomLength];
        
        for (int i = 0; i < roomLength; i++) {
            rooms[i] = getLastRoom(room_number[i]);
        }
        
        return rooms;
    }
    
    private long getLastRoom(long roomNumber) {
        if (!roomMap.containsKey(roomNumber)) {
            roomMap.put(roomNumber, roomNumber + 1);
            return roomNumber;
        }
        
        long lastRoomNumber = roomMap.get(roomNumber);
        long emptyRoomNumber = getLastRoom(lastRoomNumber);
        
        roomMap.put(roomNumber, emptyRoomNumber);
        
        return emptyRoomNumber;
    }
}

 

처음 풀는 방법을 생각해내는건 어렵지 않았습니다. 하지만 정확성은 모두 통과하는데 효율성은 통과하지 못했습니다.

#기존 풀이 방법

1. Map을 이용하여 방이 이미 배정되었는지를 지정

이 방법의 문제점은 이미 검사된 방들을 중복 검사를 하며 진행된다는 것이였습니다. 따라서 중복 검사를 최대한 제거하기 위해 Map에 배정 여부를 저장하지 않고 다음 빈 방을 저장하도록 변경했습니다.

 

import java.util.*;

//!!!! 이 방법은 효율성 테스트를 실패합니다 !!!!

class Solution {
    Map<Long, Boolean> roomMap = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] rooms = new long[room_number.length];
        
        for (int i = 0; i < room_number.length; i++) {
            long roomNumber = room_number[i];
            
            if (Objects.isNull(roomMap.get(roomNumber))) {
                roomMap.put(roomNumber, true);
                rooms[i] = roomNumber;
            } else {
                long lastRoomNumber = getLastRoom(roomNumber);
                roomMap.put(lastRoomNumber, true);
                rooms[i] = lastRoomNumber;
            }
        }
        
        return rooms;
    }
    
    private long getLastRoom(long roomNumber) {
        long lastRoomNumber = roomNumber + 1;
        while(true) {
            if (Objects.isNull(roomMap.get(lastRoomNumber))) break;
            else lastRoomNumber++;
        }
        
        return lastRoomNumber;
    }
}

 

 

2. Map에 다음 빈방을 저장

빈 방을 찾아서 Map의 Value에 저장하고 이를 통해 중복을 줄였지만 여기서도 효율성은 실패했습니다.

코드도 시간복잡도를 크게 늘릴만한 부분이 없었기 때문에 방법 찾기가 쉽지 않았습니다. 굳이 생각해보니 다음 빈방을 찾는 메서드 부분에서 중복으로 순회하는 부분이 있었습니다.

• 빈 방을 찾는 부분 (while 부분)
• 배정을 요청한 방과 그 이후의 방들을 찾은 빈 방으로 갱신 (for 부분)
•  
• 위 두 부분에서 빈 방을 찾고 다시 그 방들을 전부 다시 접근해서 갱신하는 부분이 겹친다고 생각이 되어서 수정했습니다.

 

import java.util.*;

//!!!! 이 방법은 효율성 테스트를 실패합니다 !!!!

class Solution {
    Map<Long, Long> roomMap = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        int roomLength = room_number.length;
        long[] rooms = new long[roomLength];
        
        for (int i = 0; i < roomLength; i++) {
            long roomNumber = room_number[i];
            
            if (roomMap.containsKey(roomNumber)) {
                long lastRoomNumber = getLastRoom(roomNumber);
                rooms[i] = lastRoomNumber;
            } else {
                roomMap.put(roomNumber, roomNumber+1);
                rooms[i] = roomNumber;
            }
        }
        
        return rooms;
    }
    
    private long getLastRoom(long roomNumber) {
        
        long lastRoomNumber = roomMap.get(roomNumber);
        while(roomMap.containsKey(lastRoomNumber)) {
            lastRoomNumber = roomMap.get(lastRoomNumber);
        }
        
        // 이 부분이 문제인가...?
        for (long i = roomNumber; i <= lastRoomNumber; i++) {
            roomMap.put(i, lastRoomNumber + 1);
        }
        
        return lastRoomNumber;
    }
}

 

3. 재귀를 이용해 접근 효율 조금이라도 증진

가장 위에 있는 풀이의 코드입니다.

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!