인프런 커뮤니티 질문&답변
작성한 질문수
5-f 질문입니다
작성
·
58
0
우선순위큐 크기가 가방 총 크기보다 클 때만 큐에서 빼는 로직을 작성했는데 왜 틀렸는지 궁금합니다
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll> pq;
ll n,k,ret;
int main(){
cin>>n>>k;
pair<ll,ll> v[n]; //jewelry
ll bag[k];
for (int i=0;i<n;i++){
cin>>v[i].first>>v[i].second;
}
for (int i=0;i<k;i++){
cin>>bag[i];
}
int idx=0; //bag index
sort(v,v+n);
sort(bag,bag+k);
int idx2=0;
while (idx2<n){
while (idx<k && idx2<n){
if (bag[idx]<v[idx2].first) idx++;
else{
if (pq.size()==k){
if (v[idx2].second>pq.top()){
pq.pop();
pq.push(v[idx2].second);
}
}else if (pq.size()<k) pq.push(v[idx2].second);
}
idx2++;
}
}
while (pq.size()){
ret+=pq.top(); pq.pop();
}
cout<<ret;
답변 2
0
0
안녕하세요, 인프런 AI 인턴입니다. ililil님.
질문하신 내용에 대해 설명드리겠습니다. 우선순위 큐를 사용할 때 가방의 총 크기를 확인하는 로직으로 접근하셨는데, 이 과정에서의 문제점을 아래에 설명드리겠습니다.
문제점 분석
가방과 보석 매칭:
bag와v(보석)의 정렬 순서와 비교 로직을 보면, 현재idx로 가방의 크기를 확인하고idx2로 보석의 무게를 탐색합니다.
bag[idx] < v[idx2].first이 조건을 통해 가방이 해당 보석을 담을 수 있는지를 확인하지만, 가방의 크기보다 보석의 무게가 큰 경우를 처리하지 않습니다.
우선순위 큐 조건:
- 기존의 코드는
pq의 사이즈가k보다 작을 때는v[idx2].second(보석의 가치)를pq에 추가합니다. 하지만,pq의 사이즈가 이미k와 같을 때는v[idx2].second가pq의 최솟값보다 큰 경우에만 최솟값을 업데이트합니다.
- 이 로직은 어느 정도 올바르게 작동할 수 있으나, 전체 보석을 고려한 최적의 조합을 담기 위해서는 반복문 내부에서 최대한 많은 가치를 큐에 넣고 나중에 필요하지 않은 작은 가치를 빼는 방식으로의 접근이 필수적입니다.
- 기존의 코드는
대안 제안
정렬된 보석과 가방을 효율적으로 이용:
- 보석과 가방을 정렬한 후에, 가능한 무게 내에서 가치가 높은 보석을 최대한 가치가 높은 순으로 큐에 넣어야 합니다.
- 가방 안에 담을 수 있는 보석을 큐에 추가하며, 이후 가방에 남은 공간이 있거나 가방이 채울 수 있는 가치보다 가치가 덜한 보석이 있다면 이를 교체하되 큰 가치로 업데이트합니다.
- 보석과 가방을 정렬한 후에, 가능한 무게 내에서 가치가 높은 보석을 최대한 가치가 높은 순으로 큐에 넣어야 합니다.
우선순위큐에 대한 추가 논리 적용:
- 큐의 크기가
k를 넘는 경우에 대한 명확한 처리보다는, 각 가방 단위로 최대 가치를 산정하고 이를 계속해서 업데이트하여 최종 가치를 산출하는 방식으로 로직을 보완해야 합니다.
- 큐의 크기가
아래 유사한 질문 링크에서 추가 설명을 확인할 수 있으니 보시길 추천드립니다:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.