[프로그래머스] 과제진행하기

https://school.programmers.co.kr/learn/courses/30/lessons/176962?language=java

프로그래머스

 

문제유형 : 시뮬레이션 + stack

 

이 문제는 새로운 과제를 시간 순서대로 정렬한 후에 해당 과제를 차근차근 수행해나가면서 어떤 과제를 먼저 끝냈는지 알아내면 되는 문제다. 과제를 수행할 때 주의 사항은 다음과 같다. 

- 새로운 과제를 시작할 시간이 되었으면 무조건 그 과제부터 시작해야 한다.

- 남는 시간이 생기면 멈춰뒀던 과제부터 시작한다. 멈춰둔 과제가 여러 개일 경우 가장 최근에 멈춘 과제부터 시작한다 => stack을 이용하자.

- 진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단한다.

import java.util.*;

class Solution {
    static class Plan {
        String name;
        int time;
        int startTime;
        public Plan(String name, String start, String time) {
            this.name = name;
            this.startTime = Integer.parseInt(start.substring(0,2))*60 + Integer.parseInt(start.substring(3,5));
            this.time = Integer.parseInt(time);
        }
        public String toString() {
            return name +" " + time + " "+ startTime;
        }
    }
    
    public String[] solution(String[][] plans) {
        // 1. 시작순서대로 정렬한다.
        List<Plan> planss = new ArrayList<>();
        for (String[] items : plans) {
            planss.add(new Plan(items[0], items[1], items[2]));
        }
        planss.sort((a,b) -> a.startTime - b.startTime);
        
        int size = planss.size();
        
        // 2. 순서대로 처리하다 남는건 stack 에 보관한다.
        Stack<Plan> stack = new Stack<>();
        List<String> results = new ArrayList<>();
        for (int i=0; i<size-1; i++) {
            Plan cur = planss.get(i);
            Plan next = planss.get(i+1);
    
            if (cur.startTime + cur.time > next.startTime) {
                // 현재꺼 처리중에 다음꺼 진행할 시간이 됨.
                cur.time = cur.time - (next.startTime - cur.startTime);
                stack.add(cur);     
            } else {
                // 현재꺼 처리하고 다음꺼 진행하기 까지 시간이 남음.
                results.add(cur.name);
                int remain = next.startTime - (cur.startTime+cur.time);
             
                // 스택에 남아있던거 순차 처리 진행
                while(!stack.isEmpty() && remain > 0) {
                    Plan plan = stack.peek();
                    if (plan.time > remain) {
                        plan.time -= remain;
                        remain = 0;
                    }
                    else {
                        remain -= plan.time;
                        stack.pop();
                        results.add(plan.name);
                    }
                }
            }
        }
        // 3. 남은거 처리
        results.add(planss.get(size-1).name);
        while(!stack.isEmpty()){
            results.add(stack.pop().name);
        }
        
  		// 4. results to answer 로 형태 변환
        String[] answer = new String[size];
        for(int i=0; i<size; i++) {
            answer[i] = results.get(i);
        }
        return answer;
    }
}

 

 

python

def solution(plans):
    answer = []
    # 1. 시작순서대로 정렬한다.
    plans.sort(key=lambda x: x[1])

    for i in range(len(plans)):
        name, st, time = plans[i]
        h, m = map(int, st.split(':'))
        st = h * 60 + m
        plans[i][1] = st
        plans[i][2] = int(time)

    # 2. 순서대로 처리하다 남는건 stack 에 보관한다.
    stack = []
    for i in range(len(plans)):
        if i == len(plans)-1:
            stack.append(plans[i])
            break
        cn, cst, ct = plans[i]
        nn, nst, nt = plans[i + 1]

        # 현재꺼 처리중에 다음꺼 진행할 시간이 됨.
        if cst + ct > nst:
            stack.append([cn, cst, ct - (nst - cst)])

        # 현재꺼 처리하고 다음꺼 진행하기 까지 시간이 남음.
        else:
            answer.append(cn)
            left = nst - (cst + ct)
            
            # 스택에 남아있던거 순차 처리 진행
            while left != 0 and stack:
                tn, tst, tt = stack.pop()
                if left >= tt:
                    left -= tt
                    answer.append(tn)
                else:
                    tt -= left
                    stack.append([tn, tst, tt])
                    left = 0
    # 남은거 처리
    while stack:
        tn, tst, tt = stack.pop()
        answer.append(tn)

    return answer

 

---

문제 풀이 회고

7개월 전에 Python으로 풀었던 문제를 이번에는 Java로 다시 풀었다. 두 언어로 작성된 코드의 진행 방식은 변수명과 변수 등장 순서 정도의 차이만 있을 뿐, 전체적인 흐름은 거의 동일했다. 시간복잡도도 nlogn 으로 동일하다. 

예전에 풀 때는 스택의 마지막 값을 정답 배열에 추가하지 않는 실수를 했고, 시간 계산에서도 오류가 있어 디버깅에 많은 시간을 소비했다. 이번에는 이러한 실수를 방지했지만, Java로 작성하는 데 시간이 더 걸려 전체 풀이 시간은 동일하게 1시간이 소요되었다. Python과 Java의 코드 작성 속도 차이를 다시 한번 실감할 수 있었다.