https://programmers.co.kr/learn/courses/30/lessons/64063
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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 메소드를 사용했다.
'Algorithm > 프로그래머스' 카테고리의 다른 글
[2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임 (0) | 2020.04.02 |
---|---|
[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (0) | 2020.04.02 |
[2019 카카오 개발자 겨울 인턴십] 불량 사용자 (0) | 2020.04.02 |
[2020카카오공채] 가사 검색 (0) | 2020.03.30 |
[2020카카오공채] 기둥과 보 설치 (0) | 2020.03.24 |