2019 카카오 개발자 겨울 인턴십 코딩테스트 - 호텔 방 배정(feat. Java)

문제 정보는 아래 링크를 확인해주세요!

 

[호텔 방 배정]

프로그래머스

처음 문제를 풀었을 때는 효율성 테스트라는 것을 인지하고 다음과 같이 접근했었다.

- 등록된 룸 넘버를 저장할 객체인 HashSet과  

- 등록되지 않은 룸 넘버를 저장할 객체인 ArrayList(k만큼의 번호를 초기화)

- HashSet을 검사해서 포함되어 있다면, ArrayList에서 해당 룸 넘버 다음 인덱스를 결과 값에 넣어주고

- 포함되어있지 않다면, 해당 룸 넘버를 ArrayList에서 지워주고 결과 값에 넣어준다.

- ArrayList에서 해당 룸 넘버의 다음 인덱스를 찾을 때는 리스트를 분기하면서 현재 원하는 등록 번호보다 큰 룸 넘버를 찾는 방식

 

k의 값이 Long 타입이다보니 리스트를 처음부터 돌리면 분명 시간초과가 날 것임은 인지하고 리스트에서 제거해주는 방식을 사용해서 최대한 분기문을 적게 돌릴려고 했지만, 극단적인 케이스 {1,99999999,99999999} 와 비슷한 케이스를 마주할 때 시관초과를 피하기 힘들 거라고 생각했다

 

또한, 애초에 k만큼의 Array를 만들 수 없는게 배열의 index가 Integer 타입이기 때문에 배열로 k를 접근하는 것은 무의미하다는 것을 느꼈다.

 

두 번째로 접근한 방법은 다음과 같다.

 

문제 접근 방법

- 현재 룸 넘버가 비어있는지 확인

- 현재 룸 넘버가 비어있으면 HashMap에 현재 룸 넘버와 룸 넘버 +1을 저장

- 현재 룸 넘버가 비어있지 않다면,

- HashMap에 현재 등록된 룸 넘버와 다음 룸 넘버를 확인할 룸 넘버를 저장

- while문을 통해 비어있는 룸 넘버를 탐색

- 비어있는 룸 넘버를 참조하고 있는 룸 넘버들의 value 값을 탐색된 룸 넘버로 교체

- 결과 도출

 

[소스코드]

 

package algorithm.programmers;

import java.util.*;

public class Pro64063 {

    public static long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];

        HashMap<Long,Long> room = new HashMap<>();//key   : 현재 등록된 룸 번호
                                                  //value : 다음 룸 번호를 확인하기 위한 룸 번호

        int idx = 0;//결과 배열에 저장할 인덱스

        for (long wanted : room_number) {

            if (!room.containsKey(wanted)) {//룸 번호가 등록되어 있지않을 때,

                room.put(wanted,wanted+1);
                answer[idx++] = wanted;
            } else {//룸번호가 등록되어 있을때

                Queue<Long> q = new LinkedList<>();//등록된 룸 번호들이 확인하기 위한 다음 룸 번호를 새로 바꿔주기 위함

                long next = room.get(wanted);//현재 등록된 룸 번호의 다음 룸 번호를 가져온다.

                q.add(next);

                while(room.containsKey(next)) {//다음 룸 번호가 등록 되어있는지를 검사

                    next = room.get(next);//다음 룸 번호를 next 변수와 q에 담아준다.
                    q.add(next);

                }

                answer[idx++] = next;//등록 되어있지 않은 룸 번호를 결과 배열에 담는다.

                while(!q.isEmpty()) room.put(q.poll(),next+1);//현재 등록되지 않은 룸 번호를 참조하고 있는 key들의 참조 번호를 새로 바꿔준다.

            }
        }

        //for (int i = 0; i < room_number.length; i++) System.out.println(answer[i]);

        return answer;
    }
}

 

정확성 테스트

효율성 테스트

 

ps. 나는 while문을 통해 접근했지만, 재귀함수로 접근하는 방식이 코드가 훨씬 간결하고, 코드의 중복도 일어나지 않으니 재귀로 접근하는 것도 좋을 것 같다.