[JAVA] Softeer 소프티어 금고털이

 

 

https://softeer.ai/practice/6288

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

 

1. 서론

 

언뜻 보면 막막한데 그냥 그리디? 수학? 구현? 문제이다. 그러니까 크게 어려울 것 없는 문제이다.

그런데 생각보다 정답률이 낮아서 놀랐다. (근데 그럴만한 이유가 있더라는...)

 

2. 문제 풀이

 

보석들을 배낭에 최대한으로 넣어가야 한다. 그러기 위해서 배낭에 최대한으로 넣을 수 있는 무게 w, 보석의 개수 n이 주어진다.

그 후 n개의 보석에 대해서 각각 보석의 무게와 개당 가격이 주어진다.

처음에 잘 이해가 안 갔는데 예를 들어 90, 1 이라고 하면 1개당 1이며, 70, 2라고 하면 1개당 값이 2인 것이다. 그리고 90, 70이 한 덩이가 아니라 각 1개라고 봐도 무방하다. (그냥 한 덩이인 줄 알고 좀 헤메었다.)

 

최대한으로 비싼 가격을 받기 위해선 어떻게 해야 할까? 그야 비싼 보석을 최대한 담는 것이다.

그러기 위해서는 정렬이 필요하다. 정렬의 우선순위는 다음과 같다.

 

1. 가격이 비싼 것
2. 그 수가 많은 것

 

이대로 정렬을 하면 가격이 많은 것을 최대한 많이 담을 수 있다.

 

그런데 문제는 정렬을 하는 방법이다. 사실 나는 아무 생각 없이 우선순위 큐를 제일 먼저 떠올렸다.

왜냐하면 정렬하는 우선순위가 정해져 있기 때문이다.

 

하지만 굳이 우선순위 큐를 사용하지 않아도 그냥 배열이나, ArrayList를 사용해 정렬해도 상관이 없을 것이라고 생각했다.

그런데 아니었다....

 

우선순위 큐를 사용한 풀이는 맞았지만, 혹시나 시간이 더 오래 걸릴까 봐 Arrays.sort()로 코드를 수정했는데 시간초과가 발생했다.

 

• PriorityQueue: O(log n)
• Arrays.sort: O(n log n)

 

시간복잡도가 정렬 시에 시간복잡도가 훨씬 작기 때문이었다.

이 문제의 교훈은 구현 방법이 아니라 바로 이 개념이었던 것이다....

 

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

  public static void main(String[] args) throws Exception {
    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());

    PriorityQueue<Point> q = new PriorityQueue<>(new Comparator<Point>() {
      @Override
      public int compare(Point o1, Point o2) { // 기준에 맞춰 역순으로 정렬
        if (o2.y == o1.y)
          return o2.x - o1.x;
        return o2.y - o1.y;
      }
    });

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

      q.add(new Point(x, y));
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
      Point p = q.poll();

      if (p.x <= w)
        ans += p.x * p.y;
      else
        ans += w * p.y;

      w -= p.x;

      if (w <= 0) break;
    }

    System.out.print(ans);
  }
}

 

 

간결해서 딱히 설명할 것도 없다. Point에 각각 무게, 가격을 넣어주고 내림차순으로 정렬했다.

그리고 큐에서 한 개씩 값을 뽑아 배낭에 넣으며 가격을 cnt 해줬다. 그리고 다 넣을 경우 더 돌지 않도록 break를 해줬다.