[softeer] 6288

문제

 

메모리 제약

 

입/출력

 

문제 분석

1. 무게당 가격이 높은 순으로 정렬
2. 많은 무게 순으로 결과값을 더함

 

풀이 1

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        // https://softeer.ai/practice/7374

        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(inputStreamReader);

        /*
            * 비싼 가격 순으로 정렬
            * 무게가 찰때까지 순차적으로 계산
            *
            *
         */

        // 초기값 입력
        int[] backpackKindInfo = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();
        int maxWeight = backpackKindInfo[0];
        int kind = backpackKindInfo[1];
        int money = 0;
        int curWeight = 0;

        // 무게당 가격 : [무게들...]
        HashMap<integer, arraylist<integer="">> stoneList = new HashMap<>();
        for (int i = 0; i < kind; i++) {
            int[] weightPrice = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();

//            stoneList.get(2).add(2);
            // 만약 key가 있으면 list append
            if (stoneList.containsKey(weightPrice[1])) {
                // 값 가져와서 새로운 값 add
                ArrayList oldVal =  stoneList.get(weightPrice[1]);
                int size = oldVal.size();
                for (int j = 0; j < size; j++) {
                    if (2 < oldVal.get(j)) {
                        oldVal.add(i,weightPrice[0]);
                    }
                }
                stoneList.put(weightPrice[2], oldVal);
            } else { // 처음 넣는 경우
                ArrayList newVal = new ArrayList<>(Arrays.asList(weightPrice[0]));
                stoneList.put(weightPrice[1], newVal);
            }
        }

        // 무게당 가격을 정렬
        List sortKeys = stoneList.keySet().stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());


        // 최대 무게가 넘으면 종료
        for (int i = 0; i < sortKeys.size(); i++) {
            ArrayList lists = stoneList.get(sortKeys.get(i));
            for (int j = 0; j < lists.size(); j++) {
                // 시작 전 현재 위치의 무게를 더했을때 넘는지 확인
                if (curWeight + lists.get(j) > maxWeight) {
                    money += (maxWeight - curWeight) * sortKeys.get(i);
                    break;
                } else {
                    // 현재 무게 더하기
                    curWeight += lists.get(j);
                    money += curWeight * sortKeys.get(i);
                }
            }
        }
        System.out.println(money);
    }
}</integer,>

 

실패

런타임 에러...? 
문제를 사이트에서 안보고 복사해서 intellij 넣어서 보다보니 제약조건을 다르게 보고있었다...!
제곱을 표기하지 못해서 10^4 을 104 이렇게 보여주는 식이었다...

또한 문제를 풀이를 단순하게 하였다.
가격 최대길이의 list를 만들고 index를 무게당 가격으로 생각!
각 무게들을 해당 index에 더해서 역순으로 가방이 찰때까지 더하면 될듯하다

 

풀이

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        // https://softeer.ai/practice/7374

        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(inputStreamReader);

        // 초기값 입력
        int[] backpackKindInfo = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();
        int maxWeight = backpackKindInfo[0]; // 최대 가방 무게
        int kind = backpackKindInfo[1]; // 금광 종류
        int money = 0; // 루팡 수입(?)
        int curWeight = 0;

        // 초기 배열
        int[] stoneWightList = new int[10001];

        // 무게당 가격 : 같은 가격이니까 무게 합산으로 계산
        HashMap<integer, integer=""> stoneList = new HashMap<>();
        for (int i = 0; i < kind; i++) {
            // 무게, 금액 입력받기
            int[] weightPrice = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();

            // 금액의 idx-1 에 돌 무게 합산
            stoneWightList[weightPrice[1]] +=  weightPrice[0];
        }

        // 거꾸로 내려오면서 최대 무게가 넘을때까지 진행
        for (int i = stoneWightList.length-1; i >= 0; i--) {
            int weight = stoneWightList[i];
            if (curWeight+weight>maxWeight) {// 다 못가져간다면...
                money += (maxWeight-curWeight)*(i);
                break;
            } else {
                curWeight += weight;
                money += weight*(i);
            }
        }
        System.out.println(money);
    }
}</integer,>

 

성공

뭐가 문제였는지 알고나니까 굉장히 허무하다..

 

 

 

링크

https://softeer.ai/practice/6288

Softeer - 현대자동차그룹 SW인재확보플랫폼