[2019 카카오 개발자 겨울 인턴십] 호텔 방 배정

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

프로그래머스

room_number의 크기가 최대 200,000이므로 단순 반복문으로는 풀 수 없는 문제이다.

이 문제는 유니온파인드를 이용하면 매우 간단히 풀 수 있다.

 

다만 방의 개수가 무려 10^12개이므로 모든 방에 대해 배열을 선언하는 것은 불가능하다.

따라서 unordered_map을 이용하여 방이 배정되어 merge가 일어나는 경우에만 urordered_map에 데이터를 집어넣었다.

 

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> p;

long long find(long long n) {
    if (p.find(n) == p.end()) return n;
    p[n] = find(p[n]);
    return p[n];
}

void merge(long long curr, long long next) {
    next = find(next);
    p[curr] = next;    // next에 curr를 합침
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;

    for (long long n : room_number) {
        // n이 p에 없으면 n으로 배정
        if (p.find(n) == p.end()) {
            answer.push_back(n);
            p[n] = n + 1;
        }
        // n이 p에 있으면 p에서 찾아서 배정
        else {
            long long assign_no = find(n);
            answer.push_back(assign_no);
            merge(assign_no, assign_no + 1);
        }
    }

    return answer;
}

 

처음 작성한 코드

 

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> p;

long long find(long long n) {
	if (p.find(n) == p.end()) return n;
	p[n] = find(p[n]);
	return p[n];
}

vector<long long> solution(long long k, vector<long long> room_number) {
	vector<long long> answer;

	for (long long n : room_number) {
		long long assign_no = find(n);
		answer.push_back(assign_no);
		p[assign_no] = assign_no + 1;
	}

	return answer;
}

 

이건 위에 코드랑 원리는 거의 비슷한데 좀더 짧은 코드.

다른분 코드를 보니 이렇게 짰는데 보기가 좋더라..

 

map이나 unordered_map에서 존재하지 않는 키값을 p[key] 이런 식으로 참조하게 되면 자동으로 0이 반환된다.

위의 코드에서는 절대 value가 0이 될 수 없으므로 그냥 p[n] == 0 이런 식으로 조건을 줘도 상관없으나

왠지모를 꺼림직함이 있어 find 메소드를 사용했다.