인프런 커뮤니티 질문&답변

안녕하세요 유태님 ㅎㅎ

디버깅을 해보니, 제 코드는 vec[j].first가 테스트케이스의 1, 2, 5가 나왔구요, 선생님 코드는 1과 5가 나왔습니다.

-> 아닙니다. 제 코드 또한 1, 2, 5가 나옵니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;

ll N, K;

priority_queue<ll> pq;

ll result;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> K;

	vector<pair<ll, ll>> vec(N);
	vector<ll> C(K);

	for (int i = 0; i < N; i++)
	{
		cin >> vec[i].first >> vec[i].second;
	}
	for (int i = 0; i < K; i++)
	{
		cin >> C[i];
	}

	sort(vec.begin(), vec.end());
	sort(C.begin(), C.end());

	int j = 0;
	for (int i = 0; i < K; i++)
	{
        for (; j < N && C[i] >= vec[j].first; j++)
        {
             cout << "get : " << vec[j].first << '\n';
             pq.push(vec[j].second);
        }

		if (!pq.empty())
		{
			result += pq.top();
			pq.pop();
		}
	}

	cout << result << '\n';

	return 0;
}

출력 :

get : 1

get : 2

get : 5 

조건문을 for문에 넣지 않고 if문 안에 넣게 되면 어떤 문제가 생기는지 궁금합니다. 테스트케이스는 정답처리가 되어서 오히려 더 헷갈립니다.

-> 조건(C[i] >= vec[j].first)을 for 루프에 포함시켰기 때문에, 조건이 만족되지 않으면 j를 멈추고 그다음 배낭을 처리할 때 다시 고려할 수 있습니다. 즉, 무게가 맞지 않는 물건이 나오면 루프가 바로 종료됩니다. if문으로 넣은 코드는 -> if 문으로 조건을 체크하지만, 조건을 만족하지 않아도 j가 계속 증가합니다. 그러므로 나중에 더 큰 배낭에서 담을 수 있는 물건이 스킵되어 처리되지 않을 가능성이 있습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 한유태님.

주어진 상황은 코드에서 가방의 무게에 맞는 아이템들의 선택과 관련된 문제로 보여집니다. 한유태님의 질문을 바탕으로 두 가지 부분을 설명드리겠습니다.

1. 벡터의 요소가 스킵된 이유:

   • for문 내의 조건에 따라 vec[j].first의 값을 처리하는 방법이 달라집니다. 한유태님의 코드에서 if문으로 조건을 따로 사용하시게 되면 for문의 끝까지 반복하게 되어 불필요한 연산을 수행할 가능성이 있습니다. 반면에, 선생님의 코드는 조건을 for문 내에 통합하여 자원의 낭비를 줄입니다.
     
   • if문으로 조건을 처리하면, 모든 vec[j].first가 C[i]보다 작거나 같은지를 반드시 탐색하게 되고, 그 결과로 첫 비교 후 조건을 만족하지 않는 부분을 스킵하게 되므로 2가 빠지게 됩니다.
     

2. 조건을 if문 안에 넣을 때의 문제점:

   • 조건이 별도로 처리되면 반복문이 실행되는 동안 모든 j에 대해 if문이 실행되고, 이로 인해 불필요한 연산이 추가될 수 있습니다.
     
   • for문 내에 조건을 넣어 성능을 최적화할 수 있습니다. 반복 조건과 증감 조건을 적절히 설정하면, 불필요한 if문 실행을 줄여 효율성을 높일 수 있습니다. 이러한 차이가 문제의 복잡도를 줄이고 잘못된 결과를 일으킬 가능성을 줄입니다.
     

한유태님께서 여전히 혼란스러우실 수 있습니다. 올바른 접근 방식에 따라 문제를 재해석하고 해결 방식에 집중하시면 좋겠습니다. 아래 유사한 상황에 대한 설명 링크를 참조하여 도움이 되실 수 있을 것 같습니다.

• 1-C 질문있습니다 :) - for 루프와 인덱스 처리에 대한 내용이 설명되어 있습니다.
  
• 8 - I 코드내용 질문입니다! - 인덱스 처리와 범위에 대한 유사한 질문입니다.
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.