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

프로그래머스 LV 4 호텔 방 배정 문제를 풀어봤다

1트

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        
        long[] answer = new long[room_number.length];
				//방문처리
        HashSet<Long> set = new HashSet<>();
				//다음 인덱스 저장
        HashMap<Long,Long> map = new HashMap<>();
        
        for(int i=0;i<room_number.length;i++){
            
            //없을경우 방 배정
            if(!set.contains(room_number[i])){
                set.add(room_number[i]);
                answer[i] = room_number[i];
                map.put(room_number[i],map.getOrDefault(room_number[i]+1,room_number[i]+1));
            }
            //있을경우 
            else{
                Long now = map.get(room_number[i]);
								//부모 찾기
                while(map.get(now)!=null){
                    now = map.get(now);
                }
                answer[i] = now;
                set.add(now);
                map.put(now,map.getOrDefault(now+1,now+1));
                
            }
            
        }
        return answer;
    }
}

문제해결

Union-Find의 느낌으로 풀어봤다

1. HashSet 자료구조를 사용해서 방문처리(배열을 사용할 경우 10^12 크기의 배열을 만들어야 하므로)
2. HashMap을 자료구조를 통해 다음 인덱스를 저장한다

하지만…

효율성 테스트에서 실패했다. 시간을 더 줄여야 한다

2트