[소프티어] 금고 털이 - Java

문제

---

 

• 소요 시간 : 30분
• 난이도 : LV 2

나의 풀이

---

1차

접근 방법

1. 무게당 가격이 높은 순서대로 정렬한다.

2. 가방 무게에서 가격이 높은 순서대로 차례차례 그리디하게 금속을 가져간다.

 

시간복잡도

O(N)

코드

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int n = sc.nextInt();

        int [][] list = new int[n][2];	

        for(int i=0; i<n; i++) {
            int m = sc.nextInt();
            int p = sc.nextInt();

            list[i][0] = m;
            list[i][1] = p;
        }
        
        Arrays.sort(list,(o1, o2) -> o2[1]-o1[1]);

        int answer = 0;

        // 100만
        for(int i=0; i<n; i++) {
            int m = list[i][0]; // 무게
            int p = list[i][1]; // 1gram당 가격

            if (w - m >= 0) {
                answer += m * p;
                w -= m;
            } else {
                answer += w * p;
                w = 0;
                break;
            }
        }

        System.out.print(answer);
    }
}

 

결과 : 시간초과

2차

 

접근 방법

입력 클래스인 Scanner에서 시간이 초과될 수 있다고 하여, BufferReader을 적용해보았다.

마찬가지로 출력도 BufferdWriter을 적용해보았다.

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        // StringTokenizer 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int w = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int [][] list = new int[n][2];	

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            list[i][0] = m;
            list[i][1] = p;
        }
        
        Arrays.sort(list,(o1, o2) -> o2[1]-o1[1]);

        int answer = 0;

        // 100만
        for(int i=0; i<n; i++) {
            int m = list[i][0]; // 무게
            int p = list[i][1]; // 1gram당 가격

            if (w - m >= 0) {
                answer += m * p;
                w -= m;
            } else {
                answer += w * p;
                w = 0;
                break;
            }
        }


        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 선언
        bw.write(Integer.toString(answer)); // 출력

        bw.close();
    }
}

 

결과 : 정답

 

정리

---

 

Java 입출력 클래스를 잘 익혀야겠다.