이번 문제는 참 카카오가 잘 만든 문제라고 생각이 든다.
이 문제는 그냥 풀지는 못했고 해설을 보고 풀었다.
우선 내가 처음에 정확도는 통과하지만, 효율성은 통과하지 못하는 코드를 설명하겠다.(그냥 틀렸으니까 정답코드 봐야지 하고 넘어가지 마시길..)
정확서 O, 효율성 X
#include <string>
#include <vector>
#include <set>
using namespace std;
vector<long long> answer;
set<long long> s;
void myfind(long long target){
target++;
long long ssize=s.size();
s.insert(target);
long long tssize = s.size();
if(ssize == tssize){
myfind(target);
}else{
answer.push_back(target);
}
}
vector<long long> solution(long long k, vector<long long> room_number) {
for(long long i=0;i<room_number.size();i++){
long long ssize=s.size();
s.insert(room_number[i]);
long long tssize = s.size();
if(ssize==tssize){
myfind(room_number[i]);
}else{
answer.push_back(room_number[i]);
}
}
return answer;
}이 문제에서는 set을 이용해 풀려고 했다.
왜?
이 문제는 2가지의 로직으로 이루어져 있다.
- 우선 손님이 원하는 방번호인 1에 사람이 현재 있는가?
- 비어있으면 그냥 방배정, 없으면 1보다 가장 인접하게 큰 방번호로 배정
1번 로직을 수행하기 위해서
호텔방에서 1을 찾는 탐색이 이루어져야한다.
ex). 현재 방이 1,4,5,6,7 이고, 손님이 6을 원한다면, 우선 6을 탐색해야한다.
이렇게 하기 위해서는 가장 빠른 탐색알고리즘은 이분 탐색이고 logN이다.
탐색에서 logN보다는 빠를 수가 없다.
Set에서 삽입은 최악이 아닌이상 최소 logN이고, 나의 코드에서 삽입전의 size와 삽입 후의 size를 비교해서 size가 동일하다면, 이미 방번호가 있다는 말 이므로,
숫자를 재귀적으로 하나씩 늘려가면서, set에 삽입을 해주었다.
처음에 답안을 제출할때도, 이걸 재귀적으로 숫자를 한개씩 늘려가면서 하는게 맞을까? 너무 많이 재귀를 부르는거 같은데? 싶었는데, 역시나.. 효율성에서 다 틀렸다.
결국 탐색 할 수있는 최소인 logN + 숫자를 1개씩 전부 비교가 아닌=>단시간에 가장 인접한 큰 방번호 고르는 로직을 수행해야한다.
그래서 UNION FIND 알고리즘을 사용하기로 했다.
애초에 생각해보면 예시 [1,3,4,1,3,1] 에서,
1을 넣으면 그다음 숫자 2
3을 넣으면 그다음 숫자 4
4를 넣으면 그다음 숫자 5
1을 다시 넣으면 그다음 숫자인 2
이런식으로 O(1)알고리즘을 짜면 좋을 것 같았는데 도저히 이걸 어떻게 해야할지 몰랐다.
근데 O(1)은 원래 불가능하고 엇비슷한 O(1)알고리즘이 바로 union FIND이다.
만약 위의 예시로 다시 한번해보자.
unorder_map의 특성은 key값으로 찾았는데 없으면 0을 반환한다.
1을 넣으면 room[1]=2 (그다음숫자를 넣기)
3을 넣으면 room[3]=4 ""
4를 넣으면 room[4]=5 ""
그다음에
1을 넣으면 재귀적으로 따라가기
room[1]!=0이므로
room[1]=getemptyidx(2);
room[2]==0이므로 return 2;
그럼 room[1]=2;가 되고
solution에서 room[2]=3;으로 바꾸어준다.
이렇게 되면 현재
room[1]=2;
room[2]=3;
room[3]=4;
room[4]=5;
이렇게 된다.
그다음에 3이 오면
room[1]=2;
room[2]=3;
room[3]=5;
room[4]=5;
room[5]=6;
이렇게 될것이다.
마지막으로,
1이 들어오면
room[1]!=0
그러므로 2로 가보면
room[2]!=0 다시 3으로 가보면
room[3]!=0 다시 5로 가보면
room[5]!=0 다시 6으로 가보면
room[6]==0 return 6
그러면
room[1]=6;
room[2]=6;
room[3]=6;
room[4]=5;
room[5]=6;
room[6]=7;
이렇게 될것이다.
이제 로직이 대강 이해가 되었을것이다.
근데 그냥 이렇게 끝내면 안되고, 진짜 시간복잡도가 이분탐색 or Set과 같이 logN보다 작은지 확인을 해봐야한다.
만약에 이런식으로 key value가 구성되어있다고 하자
key 1 2 3 4 5 6
value 2 3 4 5 6 7
만약 이상황에서 1이들어온다고 치자 그러면 모든 key인 2,3,4,5,6,7을 전부 훑어야 할것이다.
그러면
key 1 2 3 4 5 6 7
value 7 7 7 7 7 7 8
이렇게 변할것이다. 그러면 이건 O(N)이다.
어? 그러면 이거 O(logN)보다 큰거 아니야 싶을 수 있는데
이건 최악의 경우인것이다. 모든 경우에 그런게 아니고
최악의 O(N)이 1번 지나면
다음부터는 O(1)에 근사하게 처리가 가능하다. 만약 4가 들어오면 1번만에 8번 키로 가기 때문이다.
고로, O(1)알고리즘은 절대 아니지만, 효율적으로 logN보다 처리를 가능하게 한다.
이 문제를 아마 못푼게 1넣으면 2, 4넣으면 5 이런식으로 key value로 처리를 하고는 싶었는데
이렇게, 딱 O(1),O(logN)으로 처리를 하려니까 그 시간복잡도 틀에 목이 메어 해답을 찾지 못했다.
사실,유니온 파인드를 모르는것도 아니고,
최악의 경우가 O(N)인것이지, 또 최선의 경우에는 O(1)과 매우 근접하게 탐색이 가능하다는것도 알게 되었다.
이렇게 딱 시간복잡도에 맞추는게 아니라 유동적으로 최소 시간 복잡도를 구성하는 로직도 알게되었다는 사실이 기쁘다!
정확도O, 효율성 O
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<long long, long long> room;
long long getemptyidx(long long target){
if(room[target]==0){
//1번 방이 비어있는데 1번방을 원하면 1번을 return
return target;
}
//union-find로 처리
return room[target]=getemptyidx(room[target]);
}
vector<long long> solution(long long k, vector<long long> room_number) {
vector<long long> answer;
for(long long i=0;i<room_number.size();i++){
long long temp = room_number[i];
long long emptyidx = getemptyidx(temp);
answer.push_back(emptyidx);
room[emptyidx]=emptyidx+1;
}
return answer;
}