본문 바로가기

Algorithm

🏨 카카오 2019 겨울 인턴십: 호텔 방 배정(Lv4)

📌 문제

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

  1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
  2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
  3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
  4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

📌 제한사항

  • k는 1 이상 1012 이하인 자연수입니다.
  • room_number 배열의 크기는 1 이상 200,000 이하입니다.
  • room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.

📌 풀이

시뮬레이션으로 풀었더니 금방 해결할 수 있었다. 하지만 k의 범위가 너무 크기 때문에 효율성에서 전부 실패했다. 문제는 아래와 같이 해결 할 수 있었다.

  1. 배정받은 방을 담는 Map이 필요하다. Map은 방 번호와 다음 방 번호를 담는다.
  2. 고객이 원하는 방이 비어있는 경우, Map에 해당 방 번호와 다음 방 번호를 넣는다.
  3. 고객이 원하는 방이 비어있지 않는 경우, 재귀를 통해 다음 방 번호를 찾는다.

📌 코드

import java.util.*;
class Solution {

    @Test
    void test() {
        assertThat(solution(10, new long[]{1,3,4,1,3,1})).isEqualTo(new long[]{1,3,4,2,5,6});
    }

    private Map<Long, Long> rooms = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        for (int i = 0; i < room_number.length; i++) {
            Long roomNumber;
            if (!rooms.containsKey(room_number[i])) {
                roomNumber = room_number[i];
            } else {
                roomNumber = findRoomNumber(room_number[i]);
            }
            answer[i] = roomNumber;
            rooms.put(roomNumber, roomNumber + 1);
        }
        return answer;
    }

    private Long findRoomNumber(Long roomNumber) {
        if (!rooms.containsKey(roomNumber)) return roomNumber;
        else {
            Long temp = findRoomNumber(rooms.get(roomNumber));
            rooms.put(roomNumber, temp);
            return temp;
        }
    }
}
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

“2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난 2019년 11월 9일 오후 2시부터 6시까지 총 4시간에 걸쳐 진행되었습니다. ’19년 신입공채 1차 코딩 테스트 시에 7문제가 출제되고 5시간의 풀이 시간이 주어졌던 것과는 달리 이번 인턴 코딩 테스트는 5문제가 출제되고 4시간의 풀이 시간이 주어졌습니다. 인턴의 경우 신입 공채와는 달리 인턴 과정을 통해 추가 […]

tech.kakao.com