[프로그래머스 Lv.2] 과제 진행하기(Java) - 스택

📌 핵심 요약

• 자료구조 — 가장 최근에 멈춘 과제부터 재개하므로 스택(LIFO)
• 시뮬레이션 단위 — 1분씩 돌리지 않고 "다음 과제 시작까지 남은 시간"을 예산으로 본다
• 구조 개선 — String[]으로 상태를 들고 다니면 타입 검사가 무력해진다. 클래스로 감쌌다

 

목차

1 문제 정리

Programmers #176962

과제 진행하기

3 ≤ plans ≤ 1,000 · playtime ≤ 100

난이도: Lv.2

과제는 정해진 시각이 되면 무조건 시작한다. 진행 중이던 과제가 있다면 멈추고 새 과제로 넘어간다. 과제를 끝냈을 때 멈춰둔 과제가 있으면 가장 최근에 멈춘 것부터 이어서 진행한다.

핵심 규칙

1. 새 과제 시작 시각이 되면 진행 중이던 과제를 무조건 멈춘다.
2. 끝낸 시각에 새 과제와 멈춰둔 과제가 모두 있으면 새 과제가 우선이다.
3. 멈춰둔 과제가 여러 개면 가장 최근에 멈춘 것부터 재개한다.
4. 끝나는 시각과 새 과제 시작 시각이 같으면 끝난 것으로 판단한다.

자료구조 결정

문제 설명에 답이 그대로 적혀 있다.

가장 최근에 멈춘 과제부터 재개하므로 후입선출, 즉 스택이다. 그리고 배열이 시간순으로 정렬되어 있지 않을 수 있다는 조건이 있으므로 시작 시각 기준 정렬이 선행되어야 한다.

시각은 "hh:mm" 문자열로 주어지지만 문자열 상태로는 뺄셈도 비교도 번거롭다. 분 단위 정수로 변환해 두면 정렬 기준과 시간 계산이 모두 단순한 정수 연산이 된다.

2 시뮬레이션을 어떤 단위로 돌릴 것인가

시계를 1분씩 전진시키는 방식도 가능하지만 불필요하다.

상태가 바뀌는 시점은 과제가 시작되는 순간뿐이기 때문이다. 그렇다면 다음과 같이 볼 수 있다.

ℹ️

예산(budget)이라는 관점

과제 i를 시작한 뒤 다음 과제 i+1이 시작할 때까지 주어진 시간은 start[i+1] - start[i]분이다. 이 시간을 쓸 수 있는 예산으로 보면, 예산이 다 떨어지는 순간이 곧 다음 과제가 끼어드는 순간이다.

예산과 playtime을 비교하면 처리가 두 갈래로 나뉜다.

조건	현재 과제	이후 처리
budget < playtime	중단	남은 시간과 함께 스택에 push
budget ≥ playtime	완료	남은 예산으로 스택에서 꺼내 처리

두 번째 갈래에서 주의할 점은 스택에서 하나만 꺼내면 안 된다는 것이다. 예산이 남아 있는 한 계속 꺼내야 하고, 꺼낸 과제도 예산 안에 들어오지 않으면 남은 시간을 줄여서 다시 넣어야 한다. 반복문이 필요한 지점이다.

등호 처리도 확인해 두었다. 문제 조건에 끝나는 시각과 새 과제 시작 시각이 같으면 끝난 것으로 판단한다고 명시되어 있으므로 budget == playtime은 완료 쪽으로 분류하는 것이 맞다.

3 처음 작성한 코드

위의 방침을 그대로 옮긴 첫 풀이다. 멈춰둔 과제를 String[]에 담아 {이름, 남은시간} 형태로 스택에 넣었다.

 

Java — 첫 풀이

import java.util.*;

class Solution {
    public String[] solution(String[][] plans) {
        Deque<String[]> stack = new ArrayDeque<>();
        List<String> answerList = new ArrayList<>();

        Arrays.sort(plans, (o1, o2) -> parseTime(o1[1]) - parseTime(o2[1]));

        for (int i = 0; i < plans.length; i++) {
            String name = plans[i][0];
            int time = parseTime(plans[i][1]);
            int playtime = Integer.parseInt(plans[i][2]);

            // 마지막 과제 처리
            if (i == plans.length - 1) {
                answerList.add(name);
                while (!stack.isEmpty()) {
                    answerList.add(stack.pop()[0]);
                }
                break;
            }

            // 과제 수행시간
            int budget = parseTime(plans[i + 1][1]) - time;

            // 과제 해결 가능하면
            if (budget >= playtime) {
                answerList.add(name);
                budget -= playtime;

                // 남은 과제 해결
                while (!stack.isEmpty() && budget > 0) {
                    String[] top = stack.pop();
                    int rest = Integer.parseInt(top[1]);

                    // 남은 시간으로 과제 처리 가능하면
                    if (budget >= rest) {
                        budget -= rest;
                        answerList.add(top[0]);
                    // 처리 안 되면 다시 stack에 넣기
                    } else {
                        stack.push(new String[]{top[0], String.valueOf(rest - budget)});
                        budget = 0;
                    }
                }

            // 과제 해결 불가능하면 스택에 추가
            } else {
                stack.push(new String[]{name, String.valueOf(playtime - budget)});
            }
        }

        return answerList.toArray(new String[0]);
    }

    private int parseTime(String time) {
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
    }
}

동작에는 문제가 없다. 다만 작성하는 과정에서 실수가 반복적으로 나온 지점이 있었고, 그 위치가 전부 같은 자리였다.

실수가 몰린 자리

과제를 중단하는 상황은 두 종류다. 그리고 두 경우의 남은 시간 계산식이 다르다.

상황	기준값	저장할 값
처음 시작한 과제를 중단	playtime	playtime - budget
재개한 과제를 다시 중단	rest	rest - budget

두 식은 형태가 같아 보이지만 빼는 대상이 다르다. 여기에 String.valueOf와 Integer.parseInt가 매번 끼어들면서 표현식이 길어지고, 어떤 값을 넣고 있는지가 한눈에 들어오지 않았다.

⚠️

타입이 검증해 주지 않는다

스택의 타입이 Deque<String[]>이면 컴파일러가 확인할 수 있는 것이 없다. 잘못된 값을 넣어도, top[0]과 top[1]을 뒤바꿔도 문법상 전부 올바른 코드다. 실행하기 전까지 드러나지 않는다.

4 구조 개선

String[] 대신 클래스

스택에 담는 것은 사실 두 개의 값이 묶인 하나의 개념, 즉 멈춰둔 과제다. 이 개념에 이름을 붙여 클래스로 만들면 세 가지가 동시에 해결된다.

• String.valueOf → Integer.parseInt 왕복이 사라진다
• top[1]이 top.remain이 되어 무엇을 의미하는지 코드에 드러난다
• 남은 시간을 줄이는 작업이 top.remain -= budget 한 줄로 끝난다

 

Java — 재중단 처리 비교

// 변경 전
stack.push(new String[]{top[0], String.valueOf(rest - budget)});

// 변경 후
top.remain -= budget;
paused.push(top);

클래스를 하나 더 만드는 비용이 생기지만, 이번 문제에서는 값의 의미를 잃어버리기 쉬운 구간이 명확했으므로 감수할 만하다고 판단했다.

중첩 else를 continue로

첫 풀이는 if (해결 가능) 블록 안에 반복문이 들어가고 그 아래에 else가 붙는 구조였다. 완료 처리와 중단 처리가 서로 다른 깊이에 놓여 어느 쪽이 주된 흐름인지 읽기 어려웠다.

중단 처리를 먼저 판단해 continue로 빠져나가면 남은 코드는 전부 완료 처리다. 들여쓰기가 한 단계 줄고 흐름이 위에서 아래로 곧게 이어진다.

마지막 과제 분기는 남겨 두었다

마지막 과제는 다음 과제가 없어 예산을 계산할 수 없다. 이때 예산을 Integer.MAX_VALUE로 주면 분기 자체를 없앨 수 있다. 예산이 무한하니 현재 과제도 끝나고 반복문이 스택도 알아서 비운다.

다만 이 방식은 읽는 쪽에서 무한 예산 → 반복문이 스택을 다 비운다까지 한 단계를 더 추론해야 한다. 삼항 연산자 안에 MAX_VALUE가 들어가면 왜 무한대인지가 코드에 드러나지 않는다. 분기를 명시적으로 두는 쪽이 의도가 그대로 보인다고 판단해 첫 풀이의 구조를 유지했다.

💡

줄인다고 항상 나아지지는 않는다

분기를 없애는 기법이 있다고 해서 무조건 적용할 이유는 없다. 줄어든 분기만큼 독자가 추론해야 할 양이 늘어난다면 그대로 두는 편이 낫다.

5 최종 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    // 멈춰둔 과제: 이름 + 남은 시간
    private static class Task {
        String name;
        int remain;
        Task(String name, int remain) {
            this.name = name;
            this.remain = remain;
        }
    }

    public String[] solution(String[][] plans) {
        Arrays.sort(plans, (a, b) -> toMinute(a[1]) - toMinute(b[1]));

        Deque<Task> paused = new ArrayDeque<>();
        List<String> done = new ArrayList<>();

        for (int i = 0; i < plans.length; i++) {
            String name = plans[i][0];
            int playtime = Integer.parseInt(plans[i][2]);

            // 마지막 과제는 방해하는 과제가 없으므로 끝까지 진행한다
            if (i == plans.length - 1) {
                done.add(name);
                while (!paused.isEmpty()) {
                    done.add(paused.pop().name);
                }
                break;
            }

            // 다음 과제 시작까지 쓸 수 있는 시간
            int budget = toMinute(plans[i + 1][1]) - toMinute(plans[i][1]);

            // 시간이 부족하면 남은 시간을 기록하고 멈춘다
            if (budget < playtime) {
                paused.push(new Task(name, playtime - budget));
                continue;
            }

            // 현재 과제 완료 후 남은 시간으로 멈춰둔 과제를 이어서 진행
            done.add(name);
            budget -= playtime;

            while (!paused.isEmpty() && budget > 0) {
                Task top = paused.pop();

                if (top.remain <= budget) {
                    done.add(top.name);
                    budget -= top.remain;
                } else {
                    top.remain -= budget;
                    paused.push(top);
                    budget = 0;
                }
            }
        }

        return done.toArray(new String[0]);
    }

    private static int toMinute(String time) {
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
    }
}

예제 2 추적

i	과제	budget	동작	stack (top →)
0	music(40)	10	10 < 40 → 중단	[music:30]
1	computer(100)	10	10 < 100 → 중단	[computer:90, music:30]
2	science(50)	80	완료, 잔여 30 → computer 부족	[computer:60, music:30]
3	history(30)	—	마지막 → 완료 후 전부 pop	[ ]

결과는 [science, history, computer, music]으로 기대값과 일치한다.

시간 복잡도

정렬 O(n log n)이 지배적이다.

각 과제는 스택에 들어갔다 나오는 횟수가 제한되므로 시뮬레이션 자체는 O(n)이다. n ≤ 1,000이므로 여유롭다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.