[백준 / 골드1] 14908 구두 수선공 (Java)

문제 보기

사용한 것

• 하루에 지불할 보상금이 더 높고 다른 작업들을 덜 지연시키는 작업을 우선적으로 선택하기 위한 그리디

풀이 방법

• 작업의 우선순위는 다음과 같다.
  • 하루에 지불할 보상금이 더 높은 것
  • 다른 작업들을 덜 지연시키는 것
• 따라서 t / s가 더 작은 작업을 우선시한다.
• 만약 같다면 번호 오름차순으로 정렬한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        List<Work> works = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            works.add(new Work(i, t, s));
        }
        Collections.sort(works);
        StringBuilder sb = new StringBuilder();
        for (Work work : works) {
            sb.append(work.n).append(" ");
        }
        System.out.println(sb);
    }
}

class Work implements Comparable<Work> {

    public int n;
    public int t;
    public int s;

    public Work(int n, int t, int s) {
        this.n = n;
        this.t = t;
        this.s = s;
    }

    @Override
    public int compareTo(Work o) {
        double div1 = (double) t / (double) s;
        double div2 = (double) o.t / (double) o.s;
        if (div1 == div2) {
            return n - o.n;
        }
        return Double.compare(div1, div2);
    }
}