https://school.programmers.co.kr/learn/courses/30/lessons/42627#
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명보다는 기존 다른 코드와 다른 점을 설명하고자 한다.
https://school.programmers.co.kr/learn/courses/14743/lessons/118891
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
위 링크에서 문제에서 조금 더 고려해야 하는 부분을 알아두는 것이 좋다.
내 소감은 이렇게 풀면 안 되지만 Heap을 사용하는 문제라, Heap을 어떤 용도로 사용할까? 란 것에 초점을 맞췄다.
하지만 Heap 무조건 넣으면 안 되고, 각 요소마다 값이 2개씩이 있고 어느 쪽으로 정렬해서 넣어야 하는지 애매한 부분이 많았다.
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct cmp {
bool operator()(vector<int> a, vector<int> b) {
return a.at(1) > b.at(1);
}
};
int solution(vector<vector<int>> jobs) {
int answer = 0, j = 0, time = 0;
sort(jobs.begin(), jobs.end());
priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
while (j < jobs.size() || !pq.empty()) {
if (jobs.size() > j && time >= jobs[j][0]) {
pq.push(jobs[j++]);
continue;
}
if (!pq.empty()) {
time += pq.top()[1];
answer += time - pq.top()[0];
pq.pop();
}
else
time = jobs[j][0];
}
return answer / jobs.size();
}다른 분들의 코드를 보면 jobs을 한번 정렬해서 시간 순으로 만든다. 그리고 난 뒤 job을 훑어가면서 내 시간에 따라 heap에 넣고, heap에서 시간 계산을 해나가며 내 상태 값을 변경해 나간다.
그리고 heap에 값이 없는 경우에는 시간을 변경한다.
나는 Job을 정렬하는 것이 마음에 들지 않았다.
결국 Job을 정렬한다는 의미는 Heap을 사용해도 된다는 의미로 생각이 들었다.
그리고 무엇보다도 while문이 두 가지 행위를 한번에 하고 있었다.
1. job을 돌기
2.Heap 체킹
어쩔 수 없이 heap에서 값을 빼내가며 상태값을 바꿔야 한다. 그래도 분리하고 싶어서 최대한 분리해봤다.
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct pairFirstASC {
bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
return a.first > b.first;
}
};
struct pairSecondASC {
bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
return a.second > b.second;
}
};
int solution(vector<vector<int>> jobs) {
int answer = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, pairFirstASC> pq;
priority_queue<pair<int, int>, vector<pair<int, int>>, pairSecondASC> pq2;
for(vector<int> job: jobs) {
pq.push({job[0], job[1]});
}
int curTime = 0;
while(!pq.empty()) {
while(!pq.empty() && pq.top().first <= curTime) {
pq2.push(pq.top());
pq.pop();
}
if(pq2.empty()) {
curTime = pq.top().first;
} else if(!pq2.empty()) {
curTime += pq2.top().second;
answer += curTime - pq2.top().first;
pq2.pop();
}
}
while(!pq2.empty()) {
curTime += pq2.top().second;
answer += curTime - pq2.top().first;
pq2.pop();
}
return answer / jobs.size();
}코드가 더 늘어나긴 했지만, 재밌는 도전이었던 것 같다.
'코딩 관련 > c++' 카테고리의 다른 글
| [카카오 인턴] 보석 쇼핑 - C++ (0) | 2024.03.02 |
|---|---|
| 광물 캐기 C++ 분석 (0) | 2023.11.08 |
| 프로그래머스 2개 이하로 다른 비트 (0) | 2023.09.25 |
| 연속된 부분 수열의 합 (0) | 2023.09.02 |
| 2018 KAKAO BLIND RECRUITMENT [3차] 압축, C++ (0) | 2023.08.26 |
