Leetcode 23. Merge k Sorted Lists
문제
k개의 정렬되어 있는 list를 정렬하는 문제이다. 제일 쉽게 접근한다면 모든 list element를 하나의 vector에 넣고 전체 sort하던가 또는 counting sort하는 방식을 생각할 수 있을 것이다.
입력 조건은
- -10000 <= 각 element 크기 <= 10000
- 0 <= k <= 10000
- 각 list 길이 : 500
- 따라서 전체 element 개수는 5,000,000이다.
모든 element를 하나로 합치고 정렬하는 방식은 풀리지 않을 것이다. 반면 문제 조건에서 정수 범위가 작으니 counting sort로 풀 수 있을 것이지만 element 크기가 미정이라면? 다른 알고리즘을 써야 한다.
내가(그리고 보편적인 솔루션이 제시하는) 것은 O(nlogk) 솔루션이다.
접근
merge-sort에서 merge한 두 배열을 합칠 때, 두 배열은 모두 오름차순 정렬되어 있다. 이 때 두 배열의 제일 앞에 있는 값들만 비교하면서 더 작은 값을 merge array에 push한다. 이와 유사하게 k개의 sorted list를 merge하는 것이기 때문에 비스하게 풀 수 있다.
각 list는 모두 오름차순 정렬되어 있기 때문에 다음과 같은 접근을 사용한다.
- 정렬한 후 제일 앞에 오는 element는 [모든 list의 제일 앞에 있는 것 중 min값]이다.
- 그 값을 빼면, 해당 list의 head를 pop한다.
- 위 두 단계를 반복한다.
이다. 첫 단계는 총 k개의 리스트가 있으니 O(k), 두번째 단계는 O(1)이다. 세 번째 단계는 모든 element에 대해 이 연산을 수행해야 하므로 O(n)이다. 그러면 전체 O(nk)가 된다.
여기서 priority queue를 이용해 첫 단계를 개선할 수 있다.
- k개의 list의 제일 앞에 있는 값을 priority queue에 넣는다.
- pq.pop()으로 [list의 제일 앞에 있는 것 중 min값]을 쉽게 뽑아낼 수 있다.
- min 값을 뽑아내면 해당 list의 head를 pop하고, head->next에 있는 것을 pq에 push한다.
- 이를 통해 pq에는 항상 [list의 제일 앞에 있는 element]가 존재하게 된다.
- 단, NULL 처리를 잘 해야 한다.
이렇게 바꿈으로써 기존의 첫 단계가 항상 O(logk)로 바뀌게 된다.
개선한 코드에서 첫 단계 : O(klogk), 둘째 단계 : O(logk), 셋째 단계 : O(1 + logk), 넷째 단계 : O(n)이다. 따라서 O(klogk + nlogk) = O(nlogk)이다.
// Runtime 22 ms Beats 83.79%
// Memory 13.3 MB Beats 74.5%
struct cmp{
bool operator()(ListNode* a, ListNode* b){ // pq.top()은 min value
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
// k개의 list 제일 앞에 있는 것을 pq에 넣음. 이 때 pq에 NULL을 허용하지 않겠다.
for(ListNode* v : lists){
if(v != NULL) pq.push(v); // *** 유의! NULL인 경우 넣지 않음
}
// 새로 정렬할 Linked List
ListNode* head = new ListNode();
ListNode *tail = head;
while(!pq.empty()){
ListNode* top = pq.top(); pq.pop();
// if(top != NULL){ // pq에는 NULL이 없음
tail->next = top; // 새로 정렬할 Linked List의 끝에 push한다.
tail = tail->next;
if(top->next != NULL) pq.push(top->next); // min을 뺀 list의 다음 element를 pq에 넣는다
// }
}
return head->next;
}
};
시간복잡도
위에서 설명했듯 O(nlogk)
공간복잡도
priority queue는 총 O(k)의 공간을 사용한다.
2023 KAKAO BLIND RECRUITMENT
프로그래머스 lv3를 거의 다 푼 기념으로 남은 2023 카카오 공채 코딩테스트를 봤다. 제한시간은 5시간, 커트라인은 약 3솔(1, 2, 3 푼 경우 떨, 1, 2, 5 푼 경우 합)이었다고 한다.
요약 및 결과
4/7솔이다.
1번 : 35분에 풀었다. 뇌가 덜 풀려서 조금 헤멘 듯. 숫자 곱하는 것도 잘못 곱하기도 했고.
2번 : 1시간 16분에 풀었다. 끝에서부터 가져오면 됨을 깨닫고 simulation 문제라 생각해서 풀었다. 실수 하나 했고... 다행히 반례를 빨리 생각해내 풀었다.
3번 : 1시간 38분에 풀었다. 문제 자체가 중복순열이라는 그다지 어렵지 않는 DFS 구현을 다루기 때문에 빨리 푼 것 같다. 실수 하나 했고... 다행이 예제에서 잡혀서 빨리 디버깅했다.
4번 : 3시간에 풀었다. 문제 푸는 데는 약 45분이 걸렸는데 디버깅에 45분이 걸렸다. 실수는 2개 했고... 하나는 생각해내서 풀었고 하나는 입력을 잘못 넣었다는 것을 45분만에 찾았다.
6번 : 풀기 시작했을 때 2시간이 남았다. 좀 deep하게 내려가야 할 것 같아 보이는 DFS 문제라서 한 번 풀고 시간초과 나거나 안 풀리면 5번 풀어야지, 하고 손 대서 풀었더니 WA + TLE가 나서 스킵했다.
5번 : 풀기 시작했을 때 1.5시간이 남았다. 딱 보니 구현만 빡세게 하면 되는 문제라 구현~구현~하고 50분정도 걸려 풀었는데 어떤 반례 때문에 패스를 못했다.
7번 : 읽지도 않음
개인정보 수집 유효기간
시키는 대로 구현하면 된다. 사실상 string parsing 문제. [약관 종류, 유효기간]을 map에 넣고 필요하면 꺼내 오면 되는 식으로 하면 되고, privacies는 날짜와 약관 종류를 계산해 앞서 초기화 해 둔 map에서 값을 가져와 날짜 계산을 하면 된다. 다만 YYYY.MM.DD 형식으로 된 것의 비교가 귀찮기 때문에 모두 day로 바꾸어서 계산했다. 35분 걸렸다.
실수한 점
- month에 28을 곱해야 하는데 60을 곱했다. 정신줄 어따 놓고 왔는지...
- 시작 날짜도 포함되기 때문에 [만료일 = 날짜 + 만료기간 - 1]을 해야 한다.
map<string, int> termMap;
int date2int(string date){ // date : YYYY.MM.DD 형식
int year = stoi(date.substr(0, 4)) - 2000;
int month = stoi(date.substr(5, 2));
int day = stoi(date.substr(8, 2));
return day + month * 28 + year * 28 * 12;
}
vector<int> solution(string today, vector<string> terms, vector<string> privacies) {
for(string str : terms){
termMap[str.substr(0, 1)] = stoi(str.substr(2));
}
int currentDay = date2int(today);
vector<int> answer;
for(int i = 0; i<privacies.size(); i++){
int privacyDay = date2int(privacies[i].substr(0, 10));
string privacyType = privacies[i].substr(11);
int expiredDay = privacyDay + 28 * termMap[privacyType] - 1; // 개월 수 * 28
if(currentDay > expiredDay) answer.push_back(i+1);
}
return answer;
}
택배 배달과 수거하기
40분 걸려 풀었다. greedy + simulation 문제. 문제가 길어서 읽는 데 시간을 조금 썼다.
- 큰 index를 2번 왕복하는 것보다 작은 index를 2번 왕복하는 것이 더 낫기 때문에 큰 index부터 먼저 처리해야 한다.
- 즉슨 제일 뒤부터 처리해야 한다.
- 최대로 가져가서 제일 뒤에서부터 돌아오면서 배달할 수 있을 때까지 배달하고 돌아온다고 생각하자.
- 그리고 이게 정해지면, 정해진 집부터 제일 뒤까지 가는 길에 배달을 할 수 있다.
- 따라서 제일 뒤에서는 가지고 있는 cap이 0이다.
- 따라서 전부 배달을 끝나면 제일 뒤에서부터 가져올 수 있을 만큼 가져오고 돌아올 수 있다.
- 이 때 [배달해야 하는 마지막 집 거리, 가져와야 하는 마지막 집 거리] * 2만큼 이동한다.
- 그러면 끝이다!
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
int lastPickupIdx = n-1, lastDeliverIdx = n-1;
// *** 반례 : 끝부분이 0인 경우에는 안 가도 됨
while(lastPickupIdx >= 0 && pickups[lastPickupIdx] == 0) lastPickupIdx--;
while(lastDeliverIdx >= 0 && deliveries[lastDeliverIdx] == 0) lastDeliverIdx--;
long long answer = 0, curDelivery, curPickup;
while(1){
if(lastPickupIdx < 0 && lastDeliverIdx < 0) break; // 둘 다 끝난 경우
answer += (max(lastPickupIdx, lastDeliverIdx) + 1) * 2;
// pickup 제일 뒤부터 계산
curPickup = cap;
while(curPickup >= 0 && lastPickupIdx >= 0){
if(curPickup >= pickups[lastPickupIdx]){ // 당길 수 있으면 당김
curPickup -= pickups[lastPickupIdx];
pickups[lastPickupIdx] = 0;
lastPickupIdx--;
}
else{ // 당기지는 못할 경우 그 양만큼 줄임
pickups[lastPickupIdx] -= curPickup;
curPickup = 0;
break;
}
}
// delivery 제일 뒤부터 계산
curDelivery = cap;
while(curDelivery >= 0 && lastDeliverIdx >= 0){
if(curDelivery >= deliveries[lastDeliverIdx]){
curDelivery -= deliveries[lastDeliverIdx];
deliveries[lastDeliverIdx] = 0;
lastDeliverIdx--;
}
else{
deliveries[lastDeliverIdx] -= curDelivery;
curDelivery = 0;
break;
}
}
}
return answer;
}실수한 점
- 제일 처음에 [lastPickupIdx, lastDeliverIdx]를 n-1로 설정하는데, 만약 0인 경우는 거기 가지 않아도 된다. 끝에서부터 0이 아닐 때까지 앞으로 당겨와야 한다.
이모티콘 할인행사
16분 걸려 풀었다. 단순 구현 문제. 2번 풀면서 머리가 좀 말랑말랑해지기도 했고 문제 난이도 자체도 쉬운 편이라 빨리 푼 것 같다.
이모티콘 개수는 7개, 각각의 할인은 10%, 20%, 30%, 40%로 4개이므로 brute-force 해도 된다. 이 경우 중복순열 DFS로 각 쿠폰의 할인율을 구할 수 있다.
이렇게 각 쿠폰의 할인율을 모두 구했다면
- 모든 사용자에 대해
- 모든 이모티콘 대해 할인율이 기준보다 높으면 산다.
- 결제금이 기준 이상일 경우에는 멤버십에 가입하게 한다.
- 결제금이 기준 이하일 경우에는 그만큼 산 것으로 한다.
- 이후 1번 조건을 달성하는 경우 갱신하고, 1번 조건이 같은 경우 profit을 maximize한다.
vector<int> discounts(7); // discounts[i] : emoticon i의 할인율
vector<vector<int>> Users;
vector<int> Emoticons;
vector<int> ratio = {10, 20, 30, 40};
int userSize, emoticonSize;
int maxJoins = -1, maxProfit = -1;
int getDiscountPrice(int originPrice, int discountRatio){
// price max : 1,000,000 / 따라서 100 더 곱해도 int 범위 안
return originPrice * (100 - discountRatio) / 100;
}
void permutation(int depth, int max_depth){
if(depth == max_depth){
int numJoins = 0;
int sumProfit = 0;
for(vector<int> User : Users){ // for all user
int payPrice = 0;
for(int i = 0; i<emoticonSize; i++){ // for all emoticons
if(User[0] <= discounts[i]){ // 할인율 더 큰 경우 삼
payPrice += getDiscountPrice(Emoticons[i], discounts[i]);
}
}
if(payPrice >= User[1]) numJoins++; // 결제금이 기준 이상인 경우 join
else sumProfit += payPrice;
}
if(numJoins >= maxJoins){ // 실수 : 1번 조건과 2번 조건을 혼용했음
maxJoins = numJoins;
maxProfit = max(maxProfit, sumProfit);
}
return;
}
for(int i = 0; i<ratio.size(); i++){
discounts[depth] = ratio[i];
permutation(depth+1, max_depth);
}
}
// users[i] : [비율, 가격] / 비율보다 큰 할인율 사고 / 가격보다 크면 플러스 가입 / size 100
// emoticions[i] : 정가, 100 배수 / 10, 20, 30, 40 할인 가능
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
userSize = users.size();
emoticonSize = emoticons.size();
Users = users;
Emoticons = emoticons;
permutation(0, emoticonSize);
return {maxJoins, maxProfit};
}실수한 점
- 멤버십 인원이 더 큰 경우는 profit을 그 값으로 갱신해야 한다.
- 멤버십 인원이 같은 경우에만 profit = max(profit, 계산한 profit)해야 했다.
- 1번 조건과 2번 조건을 혼용해 예제에서 틀렸고, 다행히 예제에서 잡혀 오랜 시간 디버깅하지 않았다.
표현 가능한 이진 트리
푸는 데 1시간 30분 걸렸다. 디버깅이 45분...
일단 문제 조건에서 각 숫자가 $10^{15}$이기 때문에 모든 수를 만들어 두는 건 안 된다. 따라서 각 수가 makeable인지 판단해야 한다. 문제를 읽다보면 2진수로 어떻게 하면 되나? 라는 생각이 든다.
- 일단 full binary tree의 vertex 개수를 저장한다. numbers 원소인 $10^{15}$ 직후까지. arr라고 하자.
- $2^{1} - 1$, $2^{2} - 1$, $2^{3} - 1$, ...
- 1, 3, 7, 15, ...로 이어진다.
- 주어진 수 n을 2진수로 표현한다. O(logn)이 걸린다. n이 worst $10^{15}$인데 $2^{10}$이 약 $10^{3}$이므로 약 $2^{50}$임을 알 수 있다. 따라서 string으로 표기한다.
- arr에서 [n을 2진수로 표현한 string].length의 lower bound를 찾는다 : O(log($2^{50}$)
- [n을 2진수로 표현한 string]가 부족한 만큼 앞에 0을 채워 넣는다.
- 예를 들어 1이라면 1로 끝난다.
- 2라면 10이지만 full binary tree로 표련하기 위해서는 010로 바꾸어야 한다.
- 3이라면 11이지만 full binary tree로 표현하기 위해 011로 바꾸어야 한다.
- 4라면 100이므로 0을 추가하지 않아도 된다.
- 8이라면 1000이므로 full binary tree로 표현하기 위해서는 0001000으로 표기해야 한다.
- full binary tree로 표현하기 위해 부족한 vertex 개수를 채워 넣는 것이다.
- 이제 이 string을 양쪽으로 search해서 subtree를 만들지 못하는 경우를 찾는다.
- mid가 0인 경우 -> 범위 내 모든 게 0이어야 만들 수 있다. 그렇지 않다면 not makeable
- mid가 1인 경우 -> 왼쪽, 오른쪽이 makeable해야 makeable이다. 왼쪽/오른쪽으로 recurse
포인트는 full binary tree vertex 개수를 lower bound 해야 하고, 이후 양쪽으로 recurse하며 탐색해야 한다는 것이다.
이걸 소스코드로 표현하면 아래와 같다.
typedef long long ll;
vector<ll> treeSizes; // full binary tree의 vertex 개수
// full binary tree vertex 개수 초기화
ll MAX_VALUE = 1000000000000000;
void init(){
ll power = 2L, num = 1L;
while(1){
if(num >= MAX_VALUE) break;
num *= power;
treeSizes.push_back(num - 1);
}
}
string toBinaryString(ll n){
string result = "";
while(n){
result = to_string(n % 2) + result;
n /= 2;
}
return result;
}
// 전체 size가 n이어야 할 때 앞자리에 0을 채워줌
string fillZeros(string str, ll n){
while(str.length() != n){
str = "0" + str;
}
return str;
}
// node 개수 n을 넣었을 때 full binary tree의 node 개수
ll getFullTreeSize(ll n){
return *(lower_bound(treeSizes.begin(), treeSizes.end(), n));
}
// s.length()는 2^k-1으로 정해져 있음
bool isMakeable(string s, ll start, ll end){
if(start == end) return true; // base case : size가 1이 경우 항상 makeable
// *** 실수 : 0001000과 같은 경우를 생각하지 못함
// 가운데가 0인데 나머지에 1이 있는 경우 : 못만듬. 전부 다 0이면 makeable
// 가운데가 1인 경우 : 양 subtree를 만들 수 있어야 함
ll mid = start + (end - start) / 2;
if(s[mid] == '0'){
ll left = start, right = end;
while(left < mid){
if(s[left] == '1' || s[right] == '1') return false;
left++; right--;
}
return true;
}
bool left = isMakeable(s, start, mid-1);
bool right = isMakeable(s, mid+1, end);
if(left && right) return true; // 좌 우 모두 탐색 가능해야 full binary tree를 만들 수 있다.
else return false;
}
vector<int> solution(vector<long long> numbers) {
init();
vector<int> answer;
for(ll n : numbers){
string binaryString = toBinaryString(n); // n의 2진수 string
// n으로 full binary tree를 만든다고 생각하고 부족한 0을 채움
binaryString = fillZeros(binaryString, getFullTreeSize(binaryString.length()));
bool result = isMakeable(binaryString, 0, binaryString.length()-1); // *** 실수 : length()를 넣었음... -1 해야 함
answer.push_back(result);
}
return answer;
}실수한 점
- isMakeable 함수는 [시작 index, 끝 index]를 넣기로 정의했는데 solution() 함수에서 넣을 때 length()를 넣었다. 이것 때문에 45분을 잡아먹었다.
- 또, mid가 0이라도 그쪽에 있는 게 다 0이라면 makeable이다. 이걸 생각하지 못했다.
표 병합
처음에 보자마자 reference같은 걸 써서 같은 걸 참조하면 안되나? 라고 생각했는데 unmerge때문에 힘들거라 생각했다. 해설을 보니 이 접근이 맞았고 union-find를 사용해서 merge하면 merge 하는 쪽의 root를 가리키게 만들고 값 수정 시 해당 값만 수정해 주면 되었다. unmerge 시 전체를 검색해서 root가 같은 걸 해제하면 되었다.
command 길이는 1000이고, r, c 각각 50이므로 table 크기는 2500. 따라서 모든 command에서 r, c를 모두 순회해도 2,500,000으로 시간 내에 충분히 풀 수 있을 거라 생각하고 merge된 것들의 set을 두었다. set을 두면 전체 순회하지 않아도 find할 수 있기 때문에 이런 선택을 했다.
나머지는 문제에서 주는 대로 구현이다. 유의할 점은 string을 split하는 거? 이건 어려운 것도 아니니 나중에 코테 친다고 하면 외워두긴 해야 한다.
- linked는 merge된 cell들의 set이 있는 vector이다. 어떤 cell이 merge인지 아닌지 찾아보려면 linked를 순회하며 element의 존재 여부를 찾아야 한다. 이게 findLinkedIndex() 함수.
- update 1번 : linked의 모든 set을 순회하며 어떤 set에 입력값 [r, c]가 있다면 그 set의 모든 값에 값을 변경해 준다.
- update 2번 : 전체 board를 순회하며 값을 찾아 변경해 준다.
- merge : [r1, c1], [r2, c2] 2개의 점이 주어진다.
- 1이 병합 된 상태 + 2가 병합 된 상태 : 2를 전부 빼서 1에 넣고 값 update
- 1이 병합 된 상태 + 2가 병합되지 않은 상태 : 2를 1에 넣고 값 update
- 1이 병합되지 않은 상태 + 2가 병합 된 상태 : 1을 2의 set에 넣고 값 update
- 1이 병합되지 않은 상태 + 2가 병합되지 않은 상태 : 새로운 set을 만든다.
- 이렇게 처리하고, 원래 있던 값에 따라 문제에서 주어진 대로 처리한다.
- unmerge : findLinkedIndex() 함수를 이용해 linked를 찾고 그 안에 있는 모든 element의 값을 초기화한다.
- print : [r, c]에 있는 것을 출력해 주기만 하면 된다.
주어진 대로 구현하기만 하면 되었다.
typedef pair<int, int> pii;
// input을 공백 기준으로 split
vector<string> splitString(string input) {
vector<string> result;
istringstream iss(input);
string buffer;
while (getline(iss, buffer, ' ')) result.push_back(buffer);
return result;
}
vector<set<pii>> linked; // linked : 병합된 cell들
string EMPTY = "EMPTY";
int tableSize = 51, NOT_FOUND = -1;
vector<vector<string>> table(tableSize, vector<string>(tableSize, EMPTY));
vector<string> printResult;
// [r, c]가 속해있는 linked set의 index. 없을 시 NOT_FOUND return
int findLinkedIndex(int r, int c){
for(int i = 0; i<linked.size(); i++){
if(linked[i].find({r, c}) != linked[i].end()) return i;
}
return NOT_FOUND;
}
void UpdateOP1(int r, int c, string value){
int linkedIdx = findLinkedIndex(r, c);
if(linkedIdx == NOT_FOUND) table[r][c] = value;
else{
for(pii cell : linked[linkedIdx]){
table[cell.first][cell.second] = value;
}
}
}
void UpdateOP2(string value1, string value2){
for(int i = 0; i < tableSize; i++){
for(int j = 0; j < tableSize; j++){
if(table[i][j] == value1) table[i][j] = value2;
}
}
}
/*
두 셀 모두 값을 가진 경우 -> r1, c1의 값으로 : merge 후 UpdateOp1 실행하면 될듯?
하나만 값을 가진 경우 : 그 값을 가짐
case가 많네...
1 병합 O + 2 병합 O : 2를 전부 빼서 1에 넣고, 값을 가지고 있는 경우 처리
1 병합 O + 2 병합 X : 2를 1에 넣고 값을 가지고 있는 경우 처리 UpdateOp1
1 병합 X + 2 병합 O : 1을 2의 set에 넣고 값을 가지고 있는 경우 처리
1 병합 X + 2 병합 X : 새로운 set 만들기 + 값 가지고 있는 경우 처리
*/
void MergeOP(int r1, int c1, int r2, int c2){
if(r1 == r2 && c1 == c2) return; // *** 실수 : r1==c1으로 적음..하...
int leftLinkedIdx = findLinkedIndex(r1, c1);
int rightLinkedIdx = findLinkedIndex(r2, c2);
string leftValue = table[r1][c1], rightValue = table[r2][c2];
if(leftLinkedIdx != NOT_FOUND && rightLinkedIdx != NOT_FOUND){
if(leftLinkedIdx == rightLinkedIdx) return; // *** 이미 merge되어 있는 것을 merge하지 않게 해야 함
for(pii cell : linked[rightLinkedIdx]){
linked[leftLinkedIdx].insert(cell);
}
linked.erase(linked.begin() + rightLinkedIdx);
}
else if(leftLinkedIdx != NOT_FOUND && rightLinkedIdx == NOT_FOUND){
linked[leftLinkedIdx].insert({r2, c2});
}
else if(leftLinkedIdx == NOT_FOUND && rightLinkedIdx != NOT_FOUND){
linked[rightLinkedIdx].insert({r1, c1});
}
else{ // leftLinkedIdx == NOT_FOUND && rightLinkedIdx == NOT_FOUND
set<pii> cells; cells.insert({r1, c1}); cells.insert({r2, c2});
linked.push_back(cells);
}
if(leftValue == EMPTY && rightValue != EMPTY){
UpdateOP1(r1, c1, rightValue);
}
else{
UpdateOP1(r1, c1, leftValue);
}
}
void UnmergeOP(int r, int c){
string prevValue = table[r][c];
int linkedIdx = findLinkedIndex(r, c);
if(linkedIdx != NOT_FOUND){
for(pii cell : linked[linkedIdx]){
table[cell.first][cell.second] = EMPTY;
}
linked.erase(linked.begin() + linkedIdx);
}
table[r][c] = prevValue;
}
void PrintOP(int r, int c){
printResult.push_back(table[r][c]);
}
vector<string> solution(vector<string> commands) {
for(string command : commands){
vector<string> params = splitString(command);
if(params[0] == "UPDATE"){
if(params.size() == 4){ // 1번
int r = stoi(params[1]), c = stoi(params[2]);
UpdateOP1(r, c, params[3]);
}
else{ // 2번
UpdateOP2(params[1], params[2]);
}
}
else if(params[0] == "MERGE"){ // 3번
int r1 = stoi(params[1]), c1 = stoi(params[2]);
int r2 = stoi(params[3]), c2 = stoi(params[4]);
MergeOP(r1, c1, r2, c2);
}
else if(params[0] == "UNMERGE"){ // 4번
int r = stoi(params[1]), c = stoi(params[2]);
UnmergeOP(r, c);
}
else if(params[0] == "PRINT"){ // 5번
int r = stoi(params[1]), c = stoi(params[2]);
PrintOP(r, c);
}
}
return printResult;
}실수한 점
- 이미 merge된 [r1, c1]과 [r2, c2]를 merge한다면 아무것도 하지 않게 해야 했었다. 이 조건을 넣지 않는다면 2를 전부 빼서 1에 넣고, 해당 linked를 삭제해 버리기 때문에 오류가 난다.
- 정신줄을 잡자. r1 == r2 && c1 == c2라고 적었어야 했는데 r1 == c1 && r2 == c2라고 적었다.
미로 탈출 명령어
출발점에서 도착점까지 도달하는 keyword를 사전순으로 만들면 되는 문제. 처음에 문제를 잘못 보아서 "각 vertex를 2번만 방문할 수 있다"고 생각해서 DFS로 구현했다. 그러면 V = 5000, 각 위치마다 edge가 8개니 40000으로 시간 안에 풀 수 있을 것이라 생각했기 때문이다. 그러나 문제 조건은 "각 vertex를 2번 이상 방문할 수 있다"였다. 이렇게 되면 각 위치마다 4개의 경우의 수가 생겨 $4^{2500}$이 되어 무조건 TLE가 난다.
추후 upsolving하며 문제를 잘못 읽은 걸 깨달아 기존 DFS를 수정했다.
DFS 구현 시 사전순으로 direction을 설정해 둔다면, 만약 어떤 경로를 거쳐 도착점에 도달한다면 그 순간 최소 사전순 배열일 것이다. 그렇지 않다면 사전순으로 더 느린 탐색 결과가 도착점에 도달하기 때문. 따라서 첫 탐색이 성공한다면 그 값을 바로 리턴한다.
또 하나의 pruning으로 다음 탐색할 위치에서 도착점까지 [k - 현재 이동거리] 안에 도달하지 못한다면 무슨 수를 쓰더라도 도착점까지 도달할 수 없다. 이 두 조건이 핵심이었다.
// 순서대로 n, m, r, c, k
int maxr, maxc, exitr, exitc, targetdist;
string IMPOSSIBLE = "impossible";
string result = IMPOSSIBLE;
int dr[4] = {1, 0, 0, -1};
int dc[4] = {0, -1, 1, 0};
vector<string> direction = {"d", "l", "r", "u"};
int getDist(int r1, int c1, int r2, int c2){
return abs(r1 - r2) + abs(c1 - c2);
}
void DFS(int curDepth, int curr, int curc, string path){
if(curDepth == targetdist){ // k만큼 탐색한 경우
if(curr == exitr && curc == exitc){
if(result == IMPOSSIBLE) result = path;
else return;
}
return;
}
if(curDepth > targetdist) return;
for(int i = 0; i<4; i++){
int nextr = curr + dr[i], nextc = curc + dc[i];
if(0 <= nextr && nextr < maxr && 0 <= nextc && nextc < maxc){
// pruning *** 여기랑
if(getDist(nextr, nextc, exitr, exitc) > (targetdist - curDepth)) continue;
// deeper
DFS(curDepth + 1, nextr, nextc, path + direction[i]);
if(result != IMPOSSIBLE) return; // *** 여기
}
}
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
// initialize
x--; y--; r--; c--; // zero-indexing
maxr = n; maxc = m; exitr = r; exitc = c; targetdist = k;
if((getDist(x, y, exitr, exitc) % 2) != (k %= 2)) return IMPOSSIBLE;
DFS(0, x, y, "");
return result;
}실수한 점
- 문제를 잘못 읽었다. 제발!
추후 upsolving 시 바꾼 버전. 무조건 k만큼 탐색 후 도착 위치에 도달해 있어야 하며 사전순으로 제일 앞의 것을 탐색해야 한다. 결국 greedy 문제이다.
- 현 위치에서 d로 갈 수 있으며 + d로 이동했을 때 거리가 k-1보다 작거나 같다면 탐색 가능하므로 그곳으로 이동
- 현 위치에서 d로 갈 수 없을 때(즉 d로 이동했을 때 위치상 도착점에 도달하지 못하는 경우) l로 이동.
- 현 위치에서 d, l로 갈 수 없을 때 r로 이동
- 현 위치에서 d, l, r로 갈 수 없을 때 u로 이동
이 while문을 거지면 무조건 답이 나온다.
string IMPOSSIBLE = "impossible";
string result = "";
int getDist(int r1, int c1, int r2, int c2){
return abs(r1 - r2) + abs(c1 - c2);
}
// d l r u
string solution(int n, int m, int x, int y, int r, int c, int k) {
while(1){
if(x == r && y == c && k == 0) break;
if(getDist(x + 1, y, r, c) <= k-1 && 0 < x + 1 && x + 1 <= n){
result += "d"; x++;
}
else if(getDist(x, y-1, r, c) <= k-1 && 0 < y - 1 && y - 1 <= m){
result += "l"; y--;
}
else if(getDist(x, y+1, r, c) <= k-1 && 0 < y + 1 && y + 1 <= m){
result += "r"; y++;
}
else if(getDist(x - 1, y, r, c) <= k-1 && 0 < x - 1 && x - 1 <= n){
result += "u"; x--;
}
else return IMPOSSIBLE;
k--;
}
return result == "" ? IMPOSSIBLE : result;
}
1, 2, 3 떨어트리기
문제는 간단하지만 구현이 크게 2단계로 나뉘어서 빡센 문제.
node size가 100이기 때문에 한 탐색에 worst case O(100)의 시간이 걸린다. target 값과 target의 길이도 100이기 때문에 각각의 탐색을 모든 target이 100이 될 때까지 한다고 해도 100 * 100 * 100 = 1,000,000으로 시간 내에 풀 수 있다. 따라서 brute-force 문제.
구현은 크게 2단계로 나뉜다.
- 무조건 1씩 떨어뜨려서 target을 만들 수 있는지 없는지 판정하는 부분
- target을 만들 수 있다면 어떤 순서로 채워야 하는지 판정하는 부분
1. 첫째 단계
먼저 [무조건 1씩 떨어트려서 target을 만들 수 있는지 없는지 탐색하는 부분]은 간단하다. 일단 brute-force 탐색을 위해 graph와 edge를 설정하고 각 탐색 시 다음 vertex를 가리키게 수정한다. vector<vector<int>> edge, vector<int> vertex와 DFS() 함수를 이용해 쉽게 구현할 수 있다. DFS 탐색 시 leaf인 경우 그 곳에 쌓인다.
이렇게 쌓인 result vector의 값들을 target과 비교한다.
- result[i] > target[i]라면 target[i]를 만들 수 없다. 따라서 return IMPOSSIBLE
- result[i] <= target[i] <= 3*result[i]라면 result[i]를 적절히 조절해 target을 표현할 수 있다. 주어지는 수가 1, 2, 3이기 때문. 모든 i에 대해 이게 성립한다면 return MAKEABLE
- 아니라면, 즉 3 * result[i] < target[i]라면 아직 result가 덜 쌓인 것이므로 MAKING을 리턴하고 DFS를 더 순회한다.
2. 둘째 단계
이렇게 쌓인 result vector를 vector<vector<int>> result로 바꾸어서 순회 결과로 쌓이는 결과를 저장한다. MAKEABLE이라면 사전순으로 오는 결과를 저장해야 하기 때문에 greedy하게 subproblem을 풀면 된다.
- 앞에서부터 작은 수를 넣을 수 있다면 작은 수를 넣으면 된다.
- 남은 숫자 개수가 1이라면 그 값을 넣어 주어야 한다.
- 남은 숫자 개수가 2 이상인 경우
- 현 위치에서 1을 택했을 때 남은 숫자들로 목표값을 채울 수 있는 경우 1을 택한다.
- 현 위치에서 2을 택했을 때 남은 숫자들로 목표값을 채울 수 있는 경우 2을 택한다.
- 현 위치에서 3을 택했을 때 남은 숫자들로 목표값을 채울 수 있는 경우 3을 택한다.
이렇게 만든 결과가 답이 된다.
int vsize;
vector<vector<int>> edge; // edge[i] : vertex i부터 출발하는 edge
vector<int> vertex; // vertex[i] : vertex i가 보고 있는 child index
vector<vector<int>> result; // 순회 결과로 쌓이는 결과
vector<int> Target; // target의 전역변수
int cnt = 1;
int MAKEABLE = 1, IMPOSSIBLE = 2, MAKING = 0;
int makeable(){
for(int i = 0; i < result.size(); i++){
if(result[i].size() > Target[i]) return IMPOSSIBLE;
if(result[i].size() <= Target[i] && Target[i] <= 3 * result[i].size()) continue;
else return MAKING;
}
return MAKEABLE;
}
int DFS(int curV){
if(edge[curV].size() == 0){ // leaf
result[curV-1].push_back(cnt); cnt++;
return makeable();
}
// deeper
int nextV = edge[curV][vertex[curV]];
vertex[curV] = (vertex[curV] + 1) % edge[curV].size();
return DFS(nextV);
}
vector<int> solution(vector<vector<int>> edges, vector<int> target) {
vsize = edges.size() + 1;
vertex.resize(vsize + 1);
fill(vertex.begin(), vertex.end(), 0);
edge.resize(vsize+1);
for(vector<int> vi : edges){
edge[vi[0]].push_back(vi[1]);
}
for(vector<int>& vi : edge) sort(vi.begin(), vi.end(), less<int>());
result.resize(target.size());
Target = target;
while(1){
int DFSresult = DFS(1);
if(DFSresult == IMPOSSIBLE) return {-1};
else if(DFSresult == MAKING) continue;
else{ // MAKEABLE
vector<int> answer(cnt-1, 0);
for(int i = 0; i<result.size(); i++){
int object = Target[i];
for(int ridx = 0; ridx < result[i].size(); ridx++){
int numleft = result[i].size() - ridx;
int answeridx = result[i][ridx];
// 앞에서부터 작은 수를 너흥ㄹ 수 있다면 그 수를 넣으면 됨
// 넣을 수 있는 개수
if(numleft == 1){ // 1개짜리면 원래 값 넣어 주어야 함
answer[answeridx - 1] = object;
}
else if(object - 1 <= 3*(numleft - 1)){ // 1을 넣었을 때 나머지 값으로 충당 가능
answer[answeridx - 1] = 1;
object -= 1;
}
else if(object - 2 <= 3 * (numleft - 1)){ // 2를 ~
answer[answeridx - 1] = 2;
object -= 2;
}
else{ // 3을 ~
answer[answeridx - 1] = 3;
object -= 3;
}
}
}
return answer;
}
}
return {-1};
}
총평
문제를 푼 직후
4솔로, 합격 기준에는 넘어가지만 아슬아슬했다. 특히 4번 문제 디버깅 못했으면 그냥 떨어졌을 거 아냐. 아찔하다... 문제 푸는 속도가 아직 너무 느리고, 반례 생각을 너무 안하는 것 같다. (반례를 생각하는 게 너무 어렵다) 2번, 3번, 4번, 5번 전부 다 반례 하나때문에 시간을 훨씬 많이 썼다. indexing 실수는 없지만 문제가 주는 조건을 너무 긍정적으로 생각해서 이렇게 되었다.
또 논리는 맞게 생각했지만 타이핑치면서 잘못 적은 부분도 많다. 코드를 적고 나면 검토를 하자...
upsolving하며
6번은 문제를 잘못 읽어서(...) 못 풀었다. 접근은 맞았고, 최대 2번 visit 가능하다고 읽어서 이렇게 되었다.. 문제를 꼼꼼하게 읽자... 아.. 진짜 ㅋㅋ 사전순 정렬 순서대로 DFS하고, 만약 [어떤 결과가 만들어졌다면 그것보다 빠른 경우가 존재하지 않으므로 return]해버리면 된다. + [현 위치에서 정답까지 가지 못한다면 자르기] 2개의 기법만 사용하면 바로 풀린다. 그리고 visit 방식에 제한이 없었다면 처음부터 greedy로 풀었을 것 같다.
5번 문제는 코드 잘못된 거 찾았어도 붙잡고 있었을 것 같다. 이미 merge된거에 merge를 안한다는 조건은 없었지만 당연히 없을거라 유추하고 코드를 작성해서 예상치 못한 결과가 나왔다.
자잘자잘한 실수만 조금 줄이고, 문제를 꼼꼼하게 읽으면서 문제가 주는 제한조건을 확실하게 읽자. - 그 후에 이런 입력은? 저런 입력은? 고민해 봐야 한다. 사실상 문제 똑바로 읽었으면 6번도 솔이고 조금 더 꼼꼼하게 생각했다면 5번도 솔이다.
지금 코테 실력은 어느 정도 궤도에 올라가 있는 것 같다. 그렇게 못하지는 않는 것 같은데, 막상 까 보니 그렇게 잘하는 것 같지도 않다. 딱 커트라인에 아슬아슬하게 걸치는 것 같다. 조금 더 해서 안정적으로 통과할 수 있게 해 보자.
'PS > PS Log' 카테고리의 다른 글
| 23.03.14. 풀었던 문제들 (0) | 2023.03.14 |
|---|---|
| 23.03.13. 풀었던 문제들 (0) | 2023.03.13 |
| 23.03.11. 풀었던 문제들 (0) | 2023.03.11 |
| 23.03.10. 풀었던 문제들 (0) | 2023.03.10 |
| 23.03.09. 풀었던 문제들 (0) | 2023.03.09 |