[코딩 테스트] 소프티어(Softeer) 연습 문제 - 금고털이

코딩 테스트를 위한 소프티어(Softeer) 연습 문제 중 금고털이 문제를 풀어보았다.

 

연습 문제 - 금고털이

• 난이도 : level 2
• 정답률 : 33%

 

https://softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

 

문제 해설

금고에 금속이 있다. 이 금속들을 배낭에 담는 문제이다.

배낭은 담을 수 있는 무게가 정해져 있고 각 금속들은 무게와 무게당 가격이 정해져 있다.

이때 배낭에 가능한 비싸게 배낭을 채우는 문제이다. 톱이 있어서 금속을 자를 수도 있다.

일단 N은 10^6 이므로 최소한 O(N^2) 보다는 적은 시간복잡도를 가지도록 구현해야 한다.

톱이 있다고 해서 경우의 수가 굉장히 많아질 수 있다. 하지만 결국 가장 이득이 되는 것으로 구현하면 되므로

모두 자를 필요는 없고 정렬한 다음 애매할 때 잘라서 포함시키면 될 것이다.

내가 생각한 것은 priority queue 자료 구조이다. priority queue는 O(NlogN)의 시간 복잡도를 가지므로 문제의 제한 조건을 만족할 수 있을 것이다.

값비싼 순서대로 priority queue에 집어 넣고 이후 하나씩 꺼내면서 배낭을 채워나간다.

만약 배낭의 무게 W보다 작다면 무조건 추가하다가, 만약 배낭의 무게 W가 다 채워졌거나 넘친다면 넘치는 금속을 잘라서 필요한 만큼 배낭을 채우면 된다.

 

코드

#include<iostream>
#include<queue>

using namespace std;

struct jew {
	int weight;
	int value;
	jew(int w, int v) {
		weight = w, value = v;
	}
};

struct Compare {
	bool operator()(jew a, jew b) {
		if (a.value > b.value) {
			return false;
		}
		else if (a.value == b.value) {
			if (a.weight > b.weight) {
				return true;
			}
			else 
				return false;
		}
		else
			return true;
	}
};

int main(int argc, char** argv)
{
	priority_queue<jew, vector<jew>, Compare> pq;
	int W, n, Wi, Pi;
	cin >> W >> n;
	for (int i = 1; i <= n; i++) {
		cin >> Wi >> Pi;
		pq.push(jew(Wi,Pi));
	}
	int result = 0;
	while (!pq.empty()) {
		int cur_w = pq.top().weight;
		int cur_v = pq.top().value;
		if (W - cur_w >= 0) {
			result += cur_v * cur_w;
			W -= cur_w;
			pq.pop();
			if (W == 0) break;
		}
		else {
			result += (W * cur_v);
			break;
		}
	}
	cout << result << endl;

	return 0;
}

 

결론

여기서 배울 수 있는 것은 효과적인 정렬 혹은 priority queue를 활용하는 법이다.

priority queue에서 금속의 가치가 같은 경우 무게가 작은 순으로 포함시키도록 해서 가능한 많은 종류를 포함하도록 구현하였지만 사실 굳이 그렇게 할 필요는 없을 것 같다.