[2019 카카오 개발자 겨울 인턴쉽] 호텔 방 배정 for JAVA

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

프로그래머스

https://tech.kakao.com/2020/04/01/2019-internship-test/

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

효율성테스트를 통과하려면 테크 카카오에 올라와있는 해설을 보는 것을 추천드립니다.

 

[문제 설명]

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

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

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호	배정된 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

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

[제한사항]

• k는 1 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

---

[입출력 예]

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

 

[풀이]

1. 효율성 통과를 제외한 테스트 풀이 

 - 순서대로 원하는 방을 주고, 만약 원하는 방이 이미 차있는 방이라면 그 방 기준으로 +1을 더해 빈방을 선택해서 준다.

 - 위의 과정을 반복하여 배정된 방들의 배열을 반환해준다.

 

2. 효율성 포함 통과 풀이

 - UnionFind을 사용하여 현재 방이 가르키고 있는 가장 빠른 방을 찾는 방법으로 해결.

 - 방을 배정했으면 배정 받은 방은 자신보다 +1만큼 큰 방을 가리키는 노드가 됨.

 - 만약 다른 사람이 이미 배정 받은 방을 원할 시에는 그 방이 가리키는 방을 반환해주면 됨.

 -  1-> 2-> 3-> 4 로 배정이 돼있다면, 1, 2, 3, 4 모두 5를 가리키게 됨. 그래서 1, 2, 3, 4방 중 하나를 선택해도 바로 5번 방을 배정해줄 수 있음.

 

Union Find : https://m.blog.naver.com/ndb796/221230967614을 나동빈님 자료를 참고하여 공부하였습니다.

 

[코드]

1. 정확성 테스트만 통과

public long[] solution(long k, long[] room_number) {
        ArrayList<Long> al = new ArrayList<Long>();        //정해진 방들이 들어있는 ArrayList
        
        for(int i = 0; i < room_number.length; i++) {
            if(!al.contains(room_number[i])) {            //원하는 방이 아직 배정되지 않았다면 바로 배정.
                al.add(room_number[i]);
            }else {                                        //이미 배정이 되있다면 배정을 원하는 방보다 큰 번호의 방중 가장 작은 방을 준다. 
                long j = room_number[i];             //증가 시켜줄 숫자.
                boolean flag = true;                //while문 종료조건
                while(flag) {
                    if(!al.contains(j+1)) {            //원하는 방에서 부터 수가 큰 방중 가장 작은 방 번호.
                        al.add(j+1);
                        flag =false;
                    }                            //포함되어있지 않으면 +1한 수가 포함되있는지 확인
                    j++;
                }
            }
        }
        
        return al.stream().mapToLong(Long::longValue).toArray();
    }

 

2. 효율성 테스트도 통과

HashMap<Long, Long> hm;
    public long NextEmptyRoom(long num) {                //현재 방
        if(hm.get(num) == null) return num;                //현재 방이 배정되있지 않다면 현재 방의 번호를 반환.
        hm.put(num, NextEmptyRoom(hm.get(num)));        //(else) 배정되있다면 현재방의 부모노드를 재귀적으로 찾음 = 배정이 되있지 않은 방까지 찾아감.
        return hm.get(num);                                //결국 현재방이 가르키고있는 빈방을 반환한다.
    }
    
    public long[] solution(long k, long[] room_number) {
        hm = new HashMap<Long, Long>();                    //HashMap을 사용해 key에는 현재방, Value에는 다음방을 찍도록 한다.
        ArrayList<Long> al = new ArrayList<Long>();
        
        for(long num : room_number) {
            long emptyRoom = NextEmptyRoom(num);        //원하는 방이 비어있으면 그 방을 주고, 아니라면 순서가 가장 빠른 방을 준다.
            hm.put(emptyRoom, emptyRoom+1);                //원하는 방 -> 원하는 방 +1인 다음방.
            al.add(emptyRoom);                            //배정된 방을 기록.
        }
        
        return al.stream().mapToLong(Long::longValue).toArray();
    }

프로그래머스 테스트 케이스 통과

느낀 점 : 효율성 문제는 정말 참신하고 효율적으로 생각할 수 있어야만 해결할 수 있는 문제인 것 같다. 언젠간 나도 그렇게 될 것이라 굳게 믿고 힘내서 공부해야겠다.