백준 - 과제는 끝나지 않아!(Java, Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/17952

[접근 방법]

나중에 들어온 작업을 최대한 먼저하기 때문에 FILO 특성이 필요해보였다.

따라서, 스택으로 작업을 저장해놨다가 가장 최신(스택에 최상단) 과제를 진행하게 코드를 짰다.

스택은 어차피 배열로 구현하여 삽입이나 배출이 O(1)이므로 주어진 시간이 시간복잡도를 좌우한다.

주어진 시간이 T라면 이 알고리즘의 시간복잡도는 O(T)가 될 듯하다.

 

[Java 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;


public class Main {
    static class Work {
        private int score;
        private int minute;

        public Work(int score, int minute) {
            this.score = score;
            this.minute = minute;
        }

        public int getScore() {
            return score;
        }

        public int getMinute() {
            return minute;
        }

        public void execute() {
            this.minute--;
        }
    }

    public static void main(String[] args) throws IOException {
        int result = 0;
        try(final BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            Stack<Work> stack = new Stack<>();

            for (int i = 0; i < N; i++) {
                int[] workInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(it -> Integer.parseInt(it)).toArray();
                Work work = null;

                if(workInfo.length > 1) {
                    if (workInfo[2] == 1) {
                        result += workInfo[1];
                        continue;
                    }
                    work = new Work(workInfo[1], workInfo[2] - 1);
                    stack.push(work);
                } else {
                    if(!stack.isEmpty()) {
                        work = stack.peek();
                        work.execute();

                        if (work.getMinute() == 0) {
                            result += work.getScore();
                            stack.pop();
                        }
                    }
                }
            }
            System.out.println(result);
        }
    }
}

[Kotlin 코드]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Subject(val score: Int, var remainTime: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var totalScore = 0
    val stack = Stack<Subject>()
    var time = readLine().toInt()

    while (time-- > 0) {
        val input = readLine().split(" ").map { it.toInt() }
        // 과제가 주어지지 않음.
        if (input.size == 1) {
            if (!stack.isEmpty()) {
                // 이전에 하던 과제의 남은 시간을 줄이고 0이 되면 점수를 더함.
                stack.pop().let {
                    it.remainTime--
                    if (it.remainTime == 0) {
                        totalScore += it.score
                    } else {
                        stack.push(it)
                    }
                }
            }
        } else {
            // 새로운 과제가 주어짐.
            // 주어진 과제 시간이 1초 이하면 스택에 안 넣고 바로 점수 추가함.
            if (input[2] <= 1) {
                totalScore += input[1]
            } else {
                stack.push(Subject(input[1], input[2]-1))
            }
        }
    }

    println(totalScore)
}