[Array] Softeer level 2 금고털이 java O(n) 풀이법

https://softeer.ai/practice/6288

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

정렬을 사용한 풀이법 (O(nLogN))

• ArrayList를 하나 만든 다음 ( 금속 개수, 무게당 가격 ) 형식으로 add
• 금속 하나당 무게를 기준으로 ArrayList를 내림차순 Sort 후, for 문 돌려서 가방 총 무게를 넘게 되면 break 
• 이 때 Sort를 하게 되면 O(nLogN) 시간이 걸리게 됨

O(n) 풀이법

• 배열의 인덱스는 무게당 가격(p), 배열 값은 금속 개수를 의미하는 배열 하나를 만듬
• 입력을 받으면서 무게당 가격에 금속 개수를 누적해감
• 배열의 끝부터 시작하여 루프를 돌며 금속 개수 * 무게당 가격으로 총 가치를 더해감
• 이때 가방에 담을 수 있는 무게를 넘긴다면 가방 무게 * 무게당 가격 리턴

예를 들어, 

100 2
90 1
70 2 

의 경우 아래와 같이 배열이 구성이 될테고,

무게당 가격(p)	0	1	2	3	...	10000
금속 개수	0	90	70	0	...	0

i = 2 일때 answer = 2 * 70 , 가방 무게 = 30

i = 1 일때 가방 무게보다 금속 개수가 더 많으므로 가방 무게 * 1 = 30

따라서 140 + 30 = 170이 된다.

정렬을 하지 않기 때문에 O(n)의 시간이 걸리게 된다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int bagWeight = Integer.parseInt(st.nextToken());
        int numOfItem = Integer.parseInt(st.nextToken());
        int[] pCollection = new int[10001];
        
        for(int i = 0; i < numOfItem; i++){
            st = new StringTokenizer(in.readLine());
            int totalWeight = Integer.parseInt(st.nextToken());
            int perWeight = Integer.parseInt(st.nextToken());
            pCollection[perWeight] = pCollection[perWeight] + totalWeight; 
        }
        int answer = 0;
        for(int j = 10000; j >= 0; j--){
            if(bagWeight <= pCollection[j]){
                answer += bagWeight * j;
                break;
            }else{
                answer += j * pCollection[j];
                bagWeight -= pCollection[j];
            }
        }
        System.out.println(answer);
        in.close();
    }
}

참고 자료

https://youtu.be/oAOT0fnBLsM?si=Cp5PmKM-VKxU-qQC