https://programmers.co.kr/learn/courses/30/lessons/64063
먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.
https://tech.kakao.com/2020/04/01/2019-internship-test/
효율성 테스트가 있는 문제로 k의 범위가 크기 때문에 방을 하나하나 순차적으로 검사해주면 효율성 테스트에 실패한다.
효율성을 통과하는 방법은 위의 카카오 테크 블로그에 그림과 함께 굉장히 잘 설명되어있는데,
요청한 방이 빈방이라면 바로 배정하고 배정된 방이 바로 다음 방을 가리키도록 해준다.
요청한 방이 빈방이 아니라면 그 방이 가리키는 다음 방을 계속 찾아가며 빈방을 찾는다.
이 방법은 Union-Find 알고리즘을 사용해서 효율적으로 구현할 수 있다. 부모 노드가 다음 빈 방의 번호 값을 가지도록 해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <string>
#include <vector>
#include <map>
using namespace std;
map<long long, long long> m;
long long getNextEmptyRoom(long long num) {
if (m[num] == 0) return num;
return m[num] = getNextEmptyRoom(m[num]);
}
vector<long long> solution(long long k, vector<long long> room_number) {
vector<long long> answer;
for (long long num : room_number) {
long long emptyRoom = getNextEmptyRoom(num);
answer.push_back(emptyRoom);
m[emptyRoom] = emptyRoom + 1;
}
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
프로그래머스 [2020카카오공채] 가사 검색 c++ (3) | 2020.05.06 |
---|---|
2019 카카오 개발자 겨울 인턴십 징검다리 건너기 ( C++ ) (0) | 2020.04.15 |
2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ ) (0) | 2020.04.09 |
2019 카카오 개발자 겨울 인턴십 튜플 ( C++ ) (3) | 2020.04.09 |
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ ) (0) | 2020.04.08 |