프로그래머스 호텔 방 배정

문제

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

풀이방법 1

• 유니온 파인드 느낌으로 가는 것이다.

• 맵의 키 값에 해당 키번호에는 비어있는 바로 다음 방번호를 넣어주는 것이다

  • m[position] = position + 1;

• findset에서는 맵의 해당 키가 비어있다면 return을 해준다.

• 문제는 해당 방이 들어갈 다음 비어있는 방을 찾을 때 재귀를 많이 해야해서 효율성이 탈락한다.

소스

#include <bits/stdc++.h>

using namespace std;

#define ll long long

map<ll, ll> m;

int findset(int x)
{
    if(m[x] == 0) return x;

    return m[x] = findset(m[x]);
}


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

    for(int i = 0; i < room_number.size(); i++) 
    {

        int position = findset(room_number[i]);
        answer.push_back(position);
        m[position] = position + 1;

    }
    return answer;
}

풀이 방법 2

• set을 이용한 풀이방법이다.

• set 사람이 있는 방의 오른쪽(가장 낮은 번호의 비어있는 방 번호)를 넣는다.

• map에는 해당 방에 사람이 있는가 없는가 체크

• map[x] = 1이 되면 set에 x가 존재하면 지워줘야한다.

• set에서 이분탐색으로 o(logN)만에 x보다 큰 가장 작은 원소 (lower_bound, upper_bound 사용)

• 여기서 이상한점 있는데 이 로직에서 for each로 하면 효율성이 다 통과되지만, for문으로 돌릴 경우 효율성이 다 통과되지않는다...

  소스

#include <bits/stdc++.h>

using namespace std;

#define ll long long



map<ll, int> m;
set<ll> S;

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

    for(auto x : room_number) {
        if(m[x])
        {
            ll t=*S.lower_bound(x);
            m[t]=1;
            answer.push_back(t);
            S.erase(t);
            if(m[t+1]==0)
                S.insert(t+1);

        }
        else 
        {
            answer.push_back(x);
            m[x] = 1;
            if(S.find(x) != S.end()) {
                S.erase(x);
            }
            if(m[x + 1] == 0) {
                S.insert(x + 1);
            }
        }
    }
    return answer;
}