- 더 맵게 ( https://programmers.co.kr/learn/courses/30/lessons/42626)
제한사항을 잘 살피지 않아 한번 틀렸었다. 문제를 꼼꼼히 읽는 습관을 길러야 한다.
- scoville의 길이는 1 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
힙을 사용해야 풀 수 있는 문제
- 포함 헤더 : queue(priority_queue를 사용하기 위해), functional(최대, 최소 힙 구현을 위해)
- 선언 : priority_queue<Type, vector, greater > (greater : 최소 힙, less : 최대 힙), 3번째 자리에 sort처럼 2개의 type인수를 갖는 bool 함수를 넣어 임의의 비교가 가능하다
- greater > 여기서 끝 부분을 띄어써서 비트연산자로 오해하지 않도록 컴파일러를 배려하자
- 멤버 함수 : top, pop, size, push
- 클레스, 구조체, pair도 구현할 수 있다. 임의의 클레스나 구조체는 '<'연산자를 오버로딩하면 된다.
```
#include
#include
using namespace std;
struct a{
int start;
int end;
int value;
};
struct cmp{
bool operator()(a t, a u){
return t.value < u.value;
}
};
bool operator1()(a t, a u){
return t.value < u.value;
}
priority_queue<a,vector,cmp> pq;
priority_queue<a,vector,operator1> pq;
```
1. 라면공장( [https://programmers.co.kr/learn/courses/30/lessons/42629](https://programmers.co.kr/learn/courses/30/lessons/42629))
문제에 대한 접근법이 잘못되어 한참 헤매었다.
**내 생각에 대한 올바른 접근법(검은점 내생각, 속빈원 적절한 접근법)**
- 큰 값의 supplies를 많이 사용할 수록 운송비가 덜 든다. 하지만 stock값이 0이 되기 이전에 supplies를 필수적으로 받아야한다.
필수적으로 받아야할 공급을 받고나니 가장 큰 수는 필요 없을 경우 어떻게 처리해야할지 모르겠다.
- stock보다 작은 dates[i]들의 공급을 적어도 하나는 받아야한다.
- 그 공급들 중 가장 큰 공급을 받아야 최소한의 횟수로 공급을 받을 수 있다.
- 큰 공급을 선별하기 위해 받을 수 있는 모든 공급을 priority_queue에 넣어 가장 큰 값을 얻을 수 있도록 한다.
- 누적 stock이 k를 넘어서면 더 이상 공급받을 필요가 없다.
1. 디스크 컨트롤러 ( [https://programmers.co.kr/learn/courses/30/lessons/42627](https://programmers.co.kr/learn/courses/30/lessons/42627))
잠을 충분히 자두어 머리를 맑게 해 두자 피곤한 상태에서 문제를 푸니 머리속에 문제가 정리가 잘 되지 않아 힘들었다.
문제에서 요구한 최소의 평균을 만들기 위한 생각을 잘못했었다.
평균을 최소로 만들기 위해 내 생각으로는 작업을 길이보다 전체 걸린 시간을 우선적으로 줄여야 된다고 생각했는데
최소 길이의 작업을 먼저 할 경우가 더 많이 줄어든다.
선택 당시의 가장 짧은 작업의 요청부터 종료까지 걸린 시간을 선택하는 것이 아니라 가장 짧은 길이의 작업을 선택해야 평균이 줄어든다.
1.
댓글남기기