[2019 카카오 개발자 겨울 인턴십 코딩테스트] 문제4. 호텔 방 배정

문제풀이

 

실제 모의 코테를 칠 때 알고리즘 2 수업시간에 한번 다뤘던 스케쥴링이 생각났다.

스케쥴링 문제는 UnionFind를 활용한 문제였는데 Collapsing Find는 그대로 사용했지만 Weighted Union 말고 바로 다음 방을 골라야 되기 때문에 사용하지 않았다.

 

Collapsing Find에서는 부모를 찾고 부모를 맵핑시켜주는 것이 가장 중요하다.

 

이를 이용하면 그저 간단하게 문제를 풀 수 있다.

 

효율성 문제인 거 같아서 쫄았지만 생각보다 앞 문제보다도 간단하게 풀었던 것 같다.

소스코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
 
using namespace std;
 
map<long long, long long> mapper;
vector<long long> result;
long long wu[200001];
 
long long col_find(long long num) {
    //없을때
    long long pos;
    for (pos = num; mapper.find(pos) != mapper.end(); pos = mapper[pos]);
 
    for (long long i = num; i != pos;) {
        long long t = mapper[i];
        mapper[i] = pos;
        i = t;
    }
    return pos;
}
 
vector<long long> solution(long long k, vector<long long> room_number) {
    for (long long i = 0; i < room_number.size(); i++) {
        long long pos = col_find(room_number[i]);
        result.push_back(pos);
        mapper[pos] = pos+1;
    }
    return result;
}
 
int main() {
    vector<long long> result = solution(10, { 1,3,4,1,3,1 });
    
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << endl;
    }
}

 

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/64063

프로그래머스