[프로그래머스/JAVA] 호텔방배정

풀이

1. 다음으로 묵을 수 있는 방을 관리하는 map (parents) 사용
2. 다음으로 묵을 수 있는 방이 공실인지 아닌지 반복문으로 탐색
   • 묵을 수 없다면 현재 방을 list에 넣어 path로 관리
3. 묵을 수 잇는 곳을 찾으면 지금까지 path 노드들의 다음으로 묵을 수 있는 방을 현재노드+1로 교체

 

비고

• union-find로 풀고 싶었는데 find 함수 구현하려다가 gg 뭔가 머리속에서 그림이 안 그려졌음 ㅠㅠ

 

 

package KakaoIntern2019.P64063_호텔방배정;

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

public class Solution {

	static long[] solution(long k, long[] room_number) {
		int N = room_number.length;
		long[] answer = new long[N];
		HashMap<Long, Long> parents = new HashMap<>();

		for (int i = 0; i < N; i++) {
			long src = room_number[i];
			ArrayList<Long> child = new ArrayList<>();
			child.add(src);
			while (parents.containsKey(src)) {
				src = parents.get(src);
				child.add(src);
			}
			answer[i] = src;
			for (long l : child) {
				parents.put(l, src + 1);
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		long[] room = { 1, 3, 4, 1, 3, 1 };
		long[] r = solution(10, room);
		for (int i = 0; i < r.length; i++) {
			System.out.println(r[i]);
		}
	}

}