Programmers[64063] - 호텔 방 배정[Level4]

링크

프로그래머스

문제설명

• 순서대로 방 배정

문제풀이

• 한칸씩 건너뛰면 시간초과뜸
• 연결성이 있는 자료구조를 만들어야함
  • Union-Find
    • 10^12의 배열을 만들순 없음
    • Map으로 구현

문제코드

import java.util.HashMap;

public class Solution4 {

    public static HashMap<Long, Long> m = new HashMap<Long, Long>();   

    public static long getParent(long a) {
        //없는 방이면
        if(!m.containsKey(a)) {
        //방 생성 후 다음방 연결
            m.put(a, a + 1);
        //방 배정
            return a;
        }

        //방이 있는 방이면
        //방 연결타면서 방 연결 업데이트 후
        m.put(a, getParent(m.get(a)));
        //최종적으로 방 배정
        return m.get(a);
    }

    public static long[] solution(long k, long[] room_number) {
        int len = room_number.length;
        long[] answer = new long[len];
        for (int i = 0; i < len; i++) {
            long go=room_number[i];

            answer[i] = getParent(go);
        }
//        System.out.println(Arrays.toString(answer));
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(10,new long[]{1,3,4,1,3,1}));
    }
}

아쉬운점

• Map 생각은 했었지만 구현을 못했었음.
  • 재귀로 구현한다.
• 이게 경로압축이 되나?
  • 얻어걸린감이있는데 재귀돌면서 경로압축까지 한다...
  • room-> {1,3,4,1,3,1}
  • Map -> {1=6, 2=6, 3=6, 4=5, 5=6, 6=7}

잘한점

• 공부하자
• O(N) = N^2에서 -> N?

효율성

• 경로압축 X

	public static long getParent(long a) {
		if(!m.containsKey(a)) {
			m.put(a, a + 1);
			return a;
		}
		return getParent(m.get(a));
	}

 

• 경로압축 O

	public static long getParent(long a) {
		if(!m.containsKey(a)) {
			m.put(a, a + 1);
			return a;
		}
		m.put(a, getParent(m.get(a)));
		return m.get(a);
	}