오랜만에 올려보는 글이다. 추석 연휴가 지나고 여러곳에 지원서를 넣느라 많이 연습을 못한게 느껴진다. 이제 결과를 기다리는 만큼 다가오는 코딩 테스트를 위해 공부 할 예정이다.
꽤 흔하게 보이는 Intervals 문제를 몸풀기로 풀어봤고 오랜만에 푼만큼 좀 고전했었다.
문제의 핵심은 서로 겹치지 않는 구간을 찾아내 최소한의 그룹으로 만들면 되는 문제이다.
예) [1,5], [6,8] O -> [1,5], [5,10] X
여기서 나는 우선정렬 큐로 구간을 모두 정렬 시켜준다음에 가장 순서에 맞게 pop 을 시켜주는 그리디한 방법을 생각했는데 내 풀이가 좀 잘 안맞아서 아쉬웠다.
내가 생각한 풀이 방법은 for 룹을 두번 쓰는 거랑 똑같았고 TLE 가 나올 수 밖에 없었기 떄문에 한번에 for 룹으로 답을 찾는 방법을 생각 못했다.
class Solution {
public:
int minGroups(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
priority_queue<int,vector<int>,greater<int>> pq;
pq.push(intervals[0][1]);
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] > pq.top()) pq.pop();
pq.push(intervals[i][1]);
}
return pq.size();
}
};답을 좀 참고 했고 위에가 내 풀이 방법을 for 룹 하나로 소화시킨 방법이다. 풀이가 좀 익숙 하다고 느꼈는데 백준에서 예전에 풀었던 최소 회의실 개수 랑 똑같은 풀이였다.
문제를 풀었던 시간이 꽤 지나기도 했고 많이 잊은거 같아 그때 풀어본 풀이를 다시 참고해서 내 실수를 알았다. 이번에도 정렬을 해주어서 가장 먼저 시작하는 시간이 앞으로 가게 만들었다. 후에는 끝나는 시간을 min_heap 에 담아서 가장 먼저 끝나는 시간을 계속 유지하고 겹치지 않는 구간이 나온다면 유지하고 있는 정보를 pop 해주면서 마지막에는 남아있는 size 로 답을 내주었다.
풀이 자체가 전에 풀었던 문제와 같기 때문에 추가적인 설명은 더 안하겠지만 비슷한 유형의 문제를 또 틀려서 굉장히 아쉬웠다.
배운점:
1. 똑같은 실수 하지말자
2. Interval 문제가 나온다면 앞으로는 쭉 참고하자
