프로그래머스 | Level 2 | 과제 진행하기

Oct 21, 2024

Published byJynn

999

Programmers | Level 2 | 과제 진행하기

Problems

📘 Src: Programmers
🗂️ Cat: Simulation

󰧭 Description

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.

과제는 시작하기로 한 시각이 되면 시작합니다.
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

 Constraints

3 ≤ plans의 길이 ≤ 1,000
- plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다.
  - name : 과제의 이름을 의미합니다.
  - 2 ≤ name의 길이 ≤ 10
  - name은 알파벳 소문자로만 이루어져 있습니다.
  - name이 중복되는 원소는 없습니다.
- start : 과제의 시작 시각을 나타냅니다.
  - "hh:mm"의 형태로 "00:00" ~ "23:59" 사이의 시간값만 들어가 있습니다.
  - 모든 과제의 시작 시각은 달라서 겹칠 일이 없습니다.
  - 과제는 "00:00" ... "23:59" 순으로 시작하면 됩니다. 즉, 시와 분의 값이 작을수록 더 빨리 시작한 과제입니다.
- playtime : 과제를 마치는데 걸리는 시간을 의미하며, 단위는 분입니다.
  - 1 ≤ playtime ≤ 100
  - playtime은 0으로 시작하지 않습니다.
- 배열은 시간순으로 정렬되어 있지 않을 수 있습니다.
진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.

󰦕 Examples

plans	result
`[["math", "12:30", "40"], ["science", "12:40", "20"], ["art", "13:00", "30"]]`	`["science", "math", "art"]`
`[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]]`	`["science", "history", "computer", "music"]`
`[["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]]`	`["bbb", "ccc", "aaa"]`

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public String[] solution(String[][] plans) {
        // plans 배열을 시간순으로 정렬
        Arrays.sort(plans, (a, b) -> a[1].compareTo(b[1]));

        List<String> completedTasks = new ArrayList<>();  // 완료된 과제를 저장할 리스트
        Deque<String[]> pausedTasks = new ArrayDeque<>();  // 일시 중지된 과제를 저장할 덱
        int currentTime = convertToMinutes(plans[0][1]);  // 첫 번째 과제의 시작 시간을 분 단위로 변환
        
        for (String[] plan : plans) {
            int nextStart = convertToMinutes(plan[1]);  // 다음 과제의 시작 시각을 분으로 변환

            // 멈춰둔 과제 중 현재 시각까지 끝낼 수 있는 것들 완료
            while (!pausedTasks.isEmpty() && currentTime + Integer.parseInt(pausedTasks.peek()[2]) <= nextStart) {
                String[] completedTask = pausedTasks.pop();
                currentTime += Integer.parseInt(completedTask[2]);  // 남은 시간만큼 경과
                completedTasks.add(completedTask[0]);  // 과제 완료
            }

            // 아직 끝나지 않은 과제는 진행 시간을 업데이트
            if (!pausedTasks.isEmpty()) {
                int remainingTime = Integer.parseInt(pausedTasks.peek()[2]);
                remainingTime -= nextStart - currentTime;  // 새로운 과제 시작 전까지 경과 시간만큼 줄임
                pausedTasks.peek()[2] = String.valueOf(remainingTime);  // 남은 시간을 다시 저장
            }

            // 현재 시각을 갱신하고 새로운 과제를 스택에 넣음
            currentTime = nextStart;
            pausedTasks.push(plan);
        }

        // 남아 있는 일시 중지된 과제들을 처리
        while (!pausedTasks.isEmpty()) {
            completedTasks.add(pausedTasks.pop()[0]);
        }

        return completedTasks.toArray(new String[0]);  // 리스트를 배열로 변환하여 반환
    }

    // "hh:mm" 형식을 분으로 변환하는 유틸리티 함수
    private int convertToMinutes(String time) {
        String[] parts = time.split(":");
        return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);
    }
}

이 문제는 스택을 이용한 과제 관리와 시간 변환을 다루는 구현 문제입니다. 문제의 핵심은 과제를 시간 순서대로 처리하는 과정에서 일시 중지된 과제들을 어떻게 이어서 수행할지에 대한 로직을 설계하는 것입니다. 새로운 과제가 시작될 때, 기존에 수행 중인 과제를 일시 중지하고, 새로운 과제가 끝난 후에 일시 중지된 과제를 다시 이어서 수행하는 방식으로 진행됩니다.

1. 문제 분석

이 문제는 여러 과제를 시간순으로 처리하는 과정에서, 중단과 재개라는 상태 변화를 어떻게 효율적으로 관리할 것인가가 핵심입니다. 각 과제는 특정 시간에 시작되고, 소요 시간이 정해져 있습니다. 새로운 과제가 시작되면, 현재 진행 중이던 과제는 즉시 중단되고, 이후 새 과제가 끝난 후 중단된 과제를 이어서 처리해야 합니다. 중요한 규칙은 가장 최근에 중단된 과제부터 처리해야 한다는 점입니다. 이는 과제를 처리하는 순서가 후입선출(LIFO) 구조를 따른다는 것을 의미합니다.

따라서 이 문제의 핵심은 과제 처리 중에 발생하는 일시 중단된 상태를 효과적으로 관리하고, 시간 흐름을 적절히 계산하는 것입니다. 주어진 시간은 "hh:mm" 형식으로 표현되므로, 이를 직접 계산하기 위해 분 단위로 변환하여 처리할 필요가 있습니다. 또한, 과제 간의 시간 차이를 정확하게 계산해 중단된 과제들을 나중에 적절한 순서로 재개하는 것이 중요합니다.

이 문제의 주된 난제는 다음과 같습니다:

중단된 과제 처리: 과제가 중단된 후, 가장 최근에 중단된 과제부터 재개하는 과제 처리 방식.
시간 계산의 정확성: 과제의 시작 시각을 기준으로 남은 시간을 계산하여 적절한 타이밍에 중단된 과제를 다시 재개해야 합니다.
과제의 순차적 처리: 각 과제를 시간 순서대로 처리하며, 처리된 과제는 완료 순서대로 기록해야 합니다.

2. 접근 방식

문제를 해결하기 위한 단계는 다음과 같습니다.

과제 시작 시간 정렬: 먼저 주어진 plans 배열을 시작 시각 기준으로 정렬합니다. 문제에서는 과제들이 시간 순서대로 정렬되어 있지 않기 때문에, 이를 정렬해야 정확한 시간 흐름에 맞게 과제를 처리할 수 있습니다.
시간 변환: 주어진 시간은 "hh:mm" 형식으로 제공되므로, 이를 분 단위로 변환하여 계산을 쉽게 만듭니다. 시작 시각 간의 차이를 쉽게 구할 수 있도록 모든 시각을 분 단위로 변환하여 처리합니다. 예를 들어, "12:30"을 750분으로 변환하면 시간 차이 계산이 직관적이고 빠르게 처리될 수 있습니다.
스택을 이용한 중단된 과제 관리: 새로운 과제가 시작되면, 진행 중이던 과제는 중단됩니다. 중단된 과제들은 스택을 이용해 관리합니다. 스택은 후입선출(LIFO) 구조이므로, 가장 나중에 중단된 과제를 먼저 처리하는 문제의 요구사항을 충족시킬 수 있습니다. 과제가 끝날 때마다 스택에서 중단된 과제를 꺼내어 이어서 처리합니다.
완료된 과제 기록: 각 과제가 완료될 때 그 이름을 리스트에 기록합니다. 과제들이 완료되는 순서대로 기록하여, 모든 과제를 완료한 후에는 리스트를 배열로 변환하여 반환합니다.

이 방식은 스택을 통해 중단된 과제를 효율적으로 관리하고, 시간 계산을 통해 각 과제의 시작과 종료를 정확히 처리함으로써 문제를 해결할 수 있습니다.

3. 시간 순서 정렬 및 자료구조 초기화

먼저, 각 과제는 시간 순서대로 처리해야 하므로, plans 배열을 시작 시각 기준으로 정렬합니다. 이렇게 정렬된 배열을 통해 각 과제를 순차적으로 처리할 수 있습니다. 또한, 완료된 과제를 저장할 리스트와 일시 중지된 과제를 관리할 스택을 초기화합니다. 진행 중인 과제의 시작 시각을 관리하기 위한 변수를 설정하여, 이후의 계산에 활용합니다.

Solution.java

Arrays.sort(plans, (a, b) -> a[1].compareTo(b[1]));  // 시작 시각을 기준으로 정렬

List<String> completedTasks = new ArrayList<>();    // 완료된 과제를 저장할 리스트
Deque<String[]> pausedTasks = new ArrayDeque<>();   // 일시 중지된 과제를 관리할 스택
int currentTime = convertToMinutes(plans[0][1]);    // 첫 번째 과제의 시작 시각을 분 단위로 변환

4. 시간 단위 변환

시간 간의 비교와 계산을 쉽게 하기 위해 "hh:mm" 형식의 시각을 분 단위로 변환하는 함수가 필요합니다. 이 함수는 시간을 "hh"와 "mm"으로 나누어 분 단위로 변환해 반환합니다. 이를 통해 시각 간의 차이를 직관적으로 계산할 수 있습니다.

Solution.java

// "hh:mm" 형식의 시간을 분 단위로 변환하는 함수
private int convertToMinutes(String time) {
    String[] parts = time.split(":");  // 시각을 ':'로 분리
    return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);  // 분 단위로 변환
}

5. 과제 진행

각 과제를 차례로 처리하는 단계입니다. 우선, 각 과제의 시작 시각을 분 단위로 변환합니다. 그 후, 진행 중인 과제와 새로운 과제의 시작 시각을 비교하여, 현재 진행 중이던 과제가 완료될 수 있는지를 확인합니다. 만약 완료할 수 있다면, 해당 과제를 완료 처리하고 리스트에 기록합니다.

Solution.java

for (String[] plan : plans) {
    // 현재 과제의 시작 시각을 분 단위로 변환
    int nextStart = convertToMinutes(plan[1]);  
    
    // 진행 중인 과제와 새로운 과제 시작 시각을 비교해 처리
    while (!pausedTasks.isEmpty() && currentTime + Integer.parseInt(pausedTasks.peek()[2]) <= nextStart) {
        String[] completedTask = pausedTasks.pop();  // 진행 중이던 과제 완료
        currentTime += Integer.parseInt(completedTask[2]);  // 완료된 과제 소요 시간만큼 경과
        completedTasks.add(completedTask[0]);  // 완료된 과제 이름을 기록
    }
    ...
}

6. 중단된 과제 처리 및 상태 갱신

새로운 과제가 시작되면 현재 진행 중인 과제를 일시 중지해야 합니다. 중단된 과제는 남은 시간을 계산하여 이후에 다시 처리할 수 있도록 상태를 갱신합니다. 그리고 새로운 과제를 시작할 때는 현재 시간을 갱신하고, 스택에 새로운 과제를 추가하여 나중에 재개할 수 있도록 준비합니다.

Solution.java

for (String[] plan : plans) {
    ...

    // 아직 완료되지 않은 과제는 일시 중단 처리
    if (!pausedTasks.isEmpty()) {
        int remainingTime = Integer.parseInt(pausedTasks.peek()[2]);
        remainingTime -= nextStart - currentTime;  // 경과한 시간만큼 남은 시간 감소
        pausedTasks.peek()[2] = String.valueOf(remainingTime);  // 남은 시간을 갱신
    }
    
    // 현재 시각을 새로운 과제 시작 시각으로 갱신
    currentTime = nextStart;  
    pausedTasks.push(plan);  // 새로운 과제를 스택에 추가
}

7. 모든 과제 처리 완료

모든 과제를 순차적으로 처리한 후에도, 스택에는 여전히 중단된 과제가 남아 있을 수 있습니다. 이는 새로운 과제가 시작될 때 이전 과제가 아직 완료되지 않고 일시 중단되었기 때문입니다. 즉, 새 과제를 완료하는 동안 시간이 부족하여 이전 과제를 다 처리하지 못한 경우입니다. 이러한 중단된 과제는 스택에 저장되어 남아 있게 되며, 모든 과제를 처리한 이후에 남은 과제들을 다시 처리해야 합니다.

스택은 후입선출(LIFO) 구조를 따르기 때문에, 가장 마지막에 중단된 과제부터 차례로 완료됩니다. 이를 통해 스택에 남아 있는 모든 과제를 순차적으로 처리하고, 각 과제의 이름을 완료된 순서대로 기록합니다.

Solution.java

// 스택에 남아 있는 일시 중지된 과제를 차례로 완료 처리
while (!pausedTasks.isEmpty()) {
    completedTasks.add(pausedTasks.pop()[0]);  // 스택에서 꺼내어 완료된 과제 기록
}

8. 완료한 과제 반환

최종적으로 완료된 과제들의 이름을 기록한 리스트를 배열로 변환하여 반환합니다. 이 배열은 문제에서 요구한 과제를 완료한 순서대로 정렬된 결과입니다.

Solution.java

// 리스트를 배열로 변환하여 반환
return completedTasks.toArray(new String[0]);

󰄉 Complexity

⏳ TC: O(n log n)
💾 SC: O(n)

과제를 시작 시각에 따라 정렬하는 데 O(n log n)의 시간이 소요됩니다. 또한, 각 과제를 처리하고, 스택에서 꺼내는 과정에서는 O(n)의 추가 시간이 필요합니다. 완료된 과제와 일시 중지된 과제를 저장하기 위한 스택과 리스트를 관리하는 데 O(n)의 공간이 요구됩니다.

Algorithm
Simulation