백준: 14908번 (구두 수선공) [JAVA]

문제 링크

https://www.acmicpc.net/problem/14908

14908번: 구두 수선공

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 작업에 대한 정보를 가진 하나의 클래스 생성 (작업 번호, 작업일, 보상 금액)
   1) 추가로 이들 간의 비교 가능한 Comparable<> 구현
2. 작업에 대한 개수 N 입력 받음
3. 이후 N번에 걸쳐 받은 정보를 바탕으로 작업 클래스 생성해 우선순위 큐에 모두 저장
4. 그 다음 우선순위 큐에서 작업들을 모두 하나씩 꺼내 작업 번호 출력

 문제에서는 단순하게 주어진 작업들을 바탕으로 전체 보상금이 최소가 되도록 작업들을 정렬하는 것이다 보니, 작업들 간에 보상금을 기반으로 비교가 가능하도록 한 다음 이들을 정렬하면 된다. 우선 하나의 작업을 나타낼 수 있는 클래스를 생성한 다음, 해당 클래스에 Comparable 인터페이스를 구현해 해당 클래스 간의 우선순위가 결정될 수 있도록 한다. 작업 클래스의 우선 순위에서 가장 중요한 것을 보상금이다. 만약 A 작업을 먼저 처리하고 B 작업을 그 다음 처리한다 했을 때, 고객에게 줘야 하는 보상금의 금액은 A의 작업 일수 X B의 보상금액이다. 반대로 B 작업을 먼저하고 A 작업을 그 다음하는 경우, 보상금은 B의 작업 일수 X A의 보상금액이기 때문에, 2개의 값을 비교해 어떤 작업을 우선적으로 처리해야할 지를 알 수 있다. 추가로 만약 두 값이 같다면 문제에서는 작업 번호가 오름차순이 되도록 번호를 정렬해야 하기 때문에, 해당 부분도 포함하여 compareTo를 구현한다.
 이후 작업은 단순하다. 단순히 전체 작업의 개수 N을 입력 받고, N번에 걸쳐 작업에 대한 정보를 입력 받는다. 그리고 그때 마다 이에 해당하는 작업 정보 클래스를 생성해 우선 순위 큐에 삽입하면 된다. 이후 모든 작업 정보 클래스 생성이 끝나면 다시 순차적으로 우선순위 큐에서 작업들을 뽑아 작업의 일련 번호를 순서대로 출력하면 된다.

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Infor> pq = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {//각 작업 생성해 우선순위 큐에 삽입
            st = new StringTokenizer(br.readLine());
            int T = Integer.parseInt(st.nextToken());
            int S = Integer.parseInt(st.nextToken());

            pq.add(new Infor(i + 1, T, S));
        }

        while (!pq.isEmpty()) {//차례대로 꺼내 print
            System.out.print(pq.poll().workNum + " ");
        }

        return;
    }

    static class Infor implements Comparable<Infor>{
        int workNum, workDay, compensation;

        public Infor(int workNum, int workDay, int compensation) {
            this.workNum = workNum;
            this.workDay = workDay;
            this.compensation = compensation;
        }

        @Override
        public int compareTo(Infor o) {//compareTo 구현
            int compensationA = o.workDay * this.compensation, compensationB = this.workDay * o.compensation;

            if (compensationA > compensationB) {//현 작업을 먼저 처리하는게 더 싸다면
                return -1;
            } else if (compensationA < compensationB) {//현 작업을 먼저 처리하는게 비싸다면
                return 1;
            } else {//같다면 오름차순이 되도록 작업 번호 기준 정렬
                if (this.workNum < o.workNum) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }
    }
}

결과