프로그래머스 (C/C++, Java) 64063 : 호텔 방 배정

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

프로그래머스

---

풀이

처음에는 set을 사용해 중복을 확인하고, 중복이라면 현재 원하는 방 번호부터 하나씩 증가하며 중복을 확인하였다.

정확도 테스트는 통과하였으나 효율성 테스트를 통과하지 못 했다.

room_number가 [1,1,1,1,1,1, ... , 1]과 같은 형식으로 들어온다면 result를 구하기 위해 1부터 탐색해야 하는데 이 경우 1 ~ 2, 1 ~ 3, 1 ~ 4, ..., 1 ~ 200,000까지 일일히 확인해 효율성이 좋지 않다.

 

다른 방법이 생각나지 않아 답을 봤고 map을 사용하여 풀었다. 

해당 방이 비어 있다면 {현재 방 번호, 현재 방 번호 + 1}로 저장해 map에 {현재 방 번호, 다음 방 번호}를 저장한다.

비어있지 않다면 map에 저장해 둔 값을 차례로 꺼낸다.

{다음 방 번호} 값을 가져와 해당 방이 비었는지 확인 후, 빈 방이 나올 때까지 이 과정을 반복한다.

이 때 거쳐간 방들의 {다음 방 번호} 값 또한 현재 빈 방으로 바꿔준다. 일종의 포인터 같은 역할을 한다고 보면 될 것 같다.

이렇게 값을 갱신한다면 위에서 언급한 경우일 경우 1부터 탐색하는 게 아닌, 4, 100,000과 같은 값부터 확인하므로 효율성이 크게 개선된다.

 

 

밑의 링크를 보며 풀이를 이해했고, 더 자세한 풀이는 밑에서 확인하면 좋을 것 같다.

 

https://school.programmers.co.kr/questions/32656

프로그래머스

 

---

C/C++ 코드

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    unordered_map<long long, long long> checkDup; // 현재 방 번호, 다음 방 번호
    
    for (long long n : room_number) {
        
        // 원하는 방이 비어 있다면 추가
        if (checkDup.find(n) == checkDup.end()) {
            checkDup[n] = n + 1;
            answer.push_back(n);
        }
        else {
            vector<long long> tmp;
            
            tmp.push_back(n);
            long long nextRoomNumber = checkDup[n];
            
            // 비어 있는 방이 나올 때까지 탐색
            while (checkDup.find(nextRoomNumber) != checkDup.end()) {
                tmp.push_back(nextRoomNumber);
                nextRoomNumber = checkDup[nextRoomNumber];
            }
            
            // 현재까지 파악한 모든 방의 다음 방 정보를 갱신
            for (long long next : tmp)
                checkDup[next] = nextRoomNumber + 1;
            
            checkDup[nextRoomNumber] = nextRoomNumber + 1;
            answer.push_back(nextRoomNumber);
        }
    }
    return answer;
}

 

Java 코드

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        
        HashMap<Long, Long> checkDup = new HashMap<>();
        
        for (int i = 0; i < room_number.length; i++) {
            long r = room_number[i];
            if (checkDup.containsKey(r)) {
                List<Long> tmp = new LinkedList<>();
                tmp.add(r);
                
                Long next = checkDup.get(r);
                while (checkDup.containsKey(next)) {
                    tmp.add(next);
                    next = checkDup.get(next);
                }

                for (long t : tmp)
                    checkDup.put(t, next + 1);
                    
                checkDup.put(next, next + 1);
                answer[i] = next;
            }  
            
            else {
                checkDup.put(r, r + 1);
                answer[i] = r;
            }
        }
        return answer;
    }
}