[자바] 프로그래머스 - 호텔 방 배정 (Lv4, Java)

문제 : Programmers-호텔 방 배정

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • 자바의 HashMap을 적절하게 사용할 줄 알아야 한다. 근데 이렇게 알고리즘 분류만 봐서는 아마 풀이를 생각하긴 힘들 것 같다. 구현 난이도보다는 아이디어가 필요한 문제이다. 그룹 관련된 개념(유니온 파인드 등)이 있다면 좀 더 쉽게 생각해낼 수 있어보인다.

 

생각 과정 (오답)

* 제가 풀이를 생각하는 과정이고 오답노트처럼 적어놓은 것이므로, 이하 생각 과정에 나온 알고리즘을 모두 몰라도 문제 푸는데 지장 없습니다. 그냥 바로 풀이만 보시려면 아래쪽에 '풀이'로 넘어가시면 됩니다.

 

  아직 선택되지 않은 현재 값 이상의 값을 찾을 수 있어야 한다. 이 때, '모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.' 라고 조건이 있으므로 별도의 예외사항은 생각하지 않아도 된다. 어쨌든 아직 선택되지 않은 현재 값 이상의 값을 찾아야 하므로 처음에 생각났던 것들은 sqrt decomposition, segment tree, fenwick tree(펜윅 트리 자체론 구할 수 없을 것 같고, 머지 소트 트리를 펜윅트리로 구현하면 가능해 보인다.), binary search(TreeSet 자료구조를 통해), merge sort tree 정도가 생각났었는데, binary search로는 너무 느릴 것 같았고, k가 10^12 이므로 사실상 배열을 활용해야 하는 알고리즘들로는 메모리 초과가 무조건 날 것 같았다. 그럼 메모리 초과를 피하기 위해 데이터 압축도 필요할 것으로 생각했다(최대 room_number가 20만이므로 10^12를 20만 이내로 압축 가능). 

 

  근데 너무 복잡하게 생각하는 것 같기도 했고, 애초에 효율성 테스트를 원활히 통과 가능할지 의문이 들었다(프로그래머스도 백준처럼 시간이나 메모리 제한좀 써져있었으면 좋겠다. 생각난거 대충 구현해보고 되면 되고 아니면 아닌건 안좋은 방식이라고 본다.). 그러다가 어차피 더 큰 수만 찾으면 되므로, 한쪽방향으로 고정되는 것이고 존재하는 값들 중 더 큰수를 선택하는게 아니고, 아직 나오지 않은 수 중 선택해야 하므로 위에서 말했던 쿼리 알고리즘들은 부적합하다고 생각했다. 그래서 생각을 바꿔서 어차피 한쪽 방향이고 무조건 +1씩 올라가면 되므로 오일러 경로 테크닉(하나가 선택될 때, 그게 그래프에서 어느 지점부터 어느 지점까지 영향을 끼치는지 알기위한 테크닉)을 실시간으로 적용하면 될 것 같았다.

 

  그래서 오일러 경로 테크닉 개념(원래 이건 보통 dfs를 통해 판단하고, 개념 자체도 좀 다르다. 그러니 오일러 경로 테크닉 자체를 적용한건 아니고 그냥 개념만 가져왔다.)을 이 문제에 적용하기 적합해 보이는 union-find 알고리즘에 값 압축을 사용하면 최대 20만 이하로 표현 가능하므로 될것같아서 일단 무작정 짰다. (코드 설계도 제대로 안하고 그냥 당시에 대충 될 것 같아서 짠거라 결론적으로 이건 틀렸다. 값 압축을 하면 안된다.) 아무튼 짠 코드는 아래와 같았다.

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    int[] parents;
    HashMap<Long, Integer> comp = new HashMap<>();
    long[] rev = new long[200000];
    int compNum = 0;

    private int getCompNum(long roomNum) {return comp.get(roomNum);}
    private long getRoomNum(int compNum) {return rev[compNum];}

    private int find(int a) {
        if (parents[a] < 0)
            return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        int h = a<b?b:a;
        int l = a<b?a:b;
        parents[h] += parents[l];
        parents[l] = h;
    }

    private void compression(long[] room_number) {
        long[] tmp = Arrays.copyOf(room_number, room_number.length);
        Arrays.sort(tmp);
        for (int i = 0; i < tmp.length; i++) {
            if (comp.containsKey(tmp[i])) continue;
            int curCompNum = compNum++;
            comp.put(tmp[i], curCompNum);
            rev[curCompNum] = tmp[i];
        }
    }

    public long[] solution(long k, long[] room_number) {
        compression(room_number);
        parents = new int[compNum+1];
        Arrays.fill(parents, -1);

        long[] answer = new long[room_number.length];
        for (int i = 0; i < room_number.length; i++) {
            int cur = getCompNum(room_number[i]);
            answer[i] = getRoomNum(find(cur));
            union(cur, cur+1);
        }
        return answer;
    }
}

 

 

풀이

  위의 생각과정으로 짜고보니 당연히 틀렸고, 생각해보니 값 압축한걸 다시 원래의 10^12 값으로 변경하려면 더 복잡한 연산이 필요함을 깨달았다. 근데 위에서 사용한 풀이의 생각 과정 자체에 틀린 부분은 없었고, 단지 값 압축만 안하면 된다. 그렇다면 배열을 못쓰니 해싱을 통해 Long 값을 표현해주면 된다. 그리고 해싱을 통해 짠다면 애초에 union-find도 필요없다. 결론적으로 풀이가 매우 간단해지는데, 어느정도 아이디어가 필요한 문제가 된다. 구현 난이도 자체도 레벨4로 보기엔 많이 쉬우니 아이디어 부분이 난이도에 가중치 높게 책정된 것 같다. 구체적인 풀이는 이하 코드에 주석으로 작성해두었다.

 

 

코드 : github

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    HashMap<Long, Long> hm = new HashMap<>();

    public long[] solution(long k, long[] room_number) {	// k는 쓸 일 없다.
        long[] answer = new long[room_number.length];
        for (int i = 0; i < room_number.length; i++) {	// room_number 차례대로 순회
            long cur = room_number[i];	// 현재 방 번호
            long selectedRoom = cur;	// selectedRoom이 답변이 될 방 번호이다.
            ArrayList<Long> candidate = new ArrayList<>();	
            // union-find는 안쓰지만, 그룹핑 개념을 적용하기 위해 지나온 방 번호들을 기억해둘꺼다. 
            // 굳이 따지자면 memoization에 해당한다. 
            // 다음에 해당 번호에 도착했을 때 더 빠르게 찾아가기 위해서이다.
            
            while (hm.containsKey(selectedRoom)) {	// hm에 key가 없다면 그대로 그 방에 들어갈 수 있고, 존재한다면 그보다 큰 남는 방에 들어가야 한다.
                candidate.add(selectedRoom);	// candidate에 추가
                selectedRoom = hm.get(selectedRoom);	// 들어갈 수 있는 방이 나올때까지 다음방으로 이동
            }
            candidate.add(selectedRoom);
            
            answer[i] = selectedRoom;	// room_number[i]에 해당하는 답 기입
            for (long candi : candidate)	// candidate들 순회하며 선택된 방 번호+1로 위치를 바꿔준다.
                hm.put(candi, selectedRoom+1);
        }
        return answer;
    }
}