문제

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

해석

첫 번째 라인에는 배낭에 담을 수 있는 총 무게와 귀금속의 종류가 주어진다.
두번째 라인부터는 귀금속의 무게와 kg당 가격이 주어진다.
주어진 귀금속은 원하는 크기만큼 잘라 배낭에 담을 수 있다.
이때 배낭에 담을 수 있는 가장 비싼 가격을 출력하면된다.

구현

1. 배낭의 크기와 귀금속의 종류, 총 가격 변수를 선언한다.
2. 귀금속의 종류 만큼 반복하여 map에 귀금속의 kg당 가격을 key로 무게를 value로 담는다.(이유는 똑같은 가격이 존재 할 수도 있기 때문에 똑같은 가격일 경우 무게를 더하는 것으로 한다)
3. map을 key기준으로 가장 비싼 순으로 sort하여 가방에 담고 담긴 무게만큼 총 가격을 더한다.(총 크기에서 - key가 0 이상이면 담고 0 보다 작으면 배낭에 담길 남은 크기만큼 가격을 계산하여 더한다.)

C++

#include<iostream>
#include<map>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char** argv)
{
  	// 1.
	int bag = 0, jewelry_num = 0, total_price = 0;
	cin >> bag >> jewelry_num;

  	// 2.
	map<int, int> jewelrys;
	for (int i = 0; i < jewelry_num; ++i) {
		int weight, price;
		cin >> weight >> price;

		jewelrys[price] += weight;
	}

  	// 3.
	vector<pair<int, int>> v_jewelrys(jewelrys.begin(), jewelrys.end());
	sort(v_jewelrys.begin(), v_jewelrys.end(), greater<>());
	for (const auto &jewelry : v_jewelrys) {
		if (bag > jewelry.second) {
			bag -= jewelry.second;
			total_price = total_price + (jewelry.first * jewelry.second);
		} else if (bag != 0) {
			total_price = total_price + (jewelry.first * bag);
			break;
		}
	}

	cout << total_price;

	return 0;
}

JAVA(테스트 케이스6번 틀렸음)

import java.util.*;
import java.io.*;

public class Main
{
  	// 1.
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new  InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int bag = Integer.parseInt(st.nextToken());
        int jewelry_num = Integer.parseInt(st.nextToken());

  		// 2.
        Map<Integer, Integer> jewelrys = new HashMap<>();
        for (int i = 0; i < jewelry_num; ++i) {
            StringTokenizer st_j = new StringTokenizer(bf.readLine(), " ");
            int weight = Integer.parseInt(st_j.nextToken());
            int price = Integer.parseInt(st_j.nextToken());
            Map<Integer, Integer> jewelry = new HashMap<>();
            jewelry.put(price, weight);

            jewelry.forEach((key, value) -> jewelrys.merge(key, value, (v1, v2) -> v1 + v2));
        }

        List<Integer> keySet = new ArrayList<>(jewelrys.keySet());
        Collections.reverse(keySet);

  		// 3.
        int total_price = 0;
        for (Integer key : keySet) {
            if(bag > jewelrys.get(key)) {
                bag -= jewelrys.get(key);
			    total_price = total_price + (key * jewelrys.get(key));
            } else if (bag != 0) {
                total_price = total_price + (key * bag);
                break;
            }
        }

        System.out.println(total_price);
    }
}

Python

import sys
import heapq

# 1.
bag, jewelry_num = map(int, sys.stdin.readline().split())

# 다음과 같이 풀 수도 있다.
# jewelrys = [list(map(int, input().split())) for _ in range(jewelry_num)]
# jewels.sort(key=lambda x: x[1], reverse=True)

# 2.
jewelrys = []
for _ in range(jewelry_num):
    weight, price = map(int, sys.stdin.readline().split())
    heapq.heappush(jewelrys, (-price, -weight))

total = 0

// 3.
for _ in range(jewelry_num):
    price, weight = heapq.heappop(jewelrys)
    price = -price
    weight = - weight
    if(bag > weight):
        bag -= weight
        total = total + (weight * price)
    elif(bag != 0):
        total = total + (bag * price)
        break

print(total)

새로 알게 된 부분

python
1. heapq.heappush(heap, item)
Heap은 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 완전 이진 트리 (Complete Binary Tree)를 기본으로 가진다.
오름차순으로 정렬되고 내림차순 정렬로는 되지 않는것 같다. 그래서 -를 붙여 내림차순과 같이 정렬해서 사용하였다.

틀린문제

java
https://velog.io/@frobenius/Softeer-%EA%B8%88%EA%B3%A0%ED%84%B8%EC%9D%B4-java 에 따르면 PriorityQueue를 사용해야 한다고 추측이 된다고 하는데 JAVA를 잘 몰라서 이부분은 따로 스터디를 진행해보아야 할 것 같다.