[Programmers] 과제 진행하기 (PYTHON, JAVA)

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

프로그래머스

 

하..문제 잘못이해해서 몇시간을 날렸다.

예제테케는 모두 통과해서....뭘 잘못한건지 한참을 고민했다.대체뭐가틀린거지!?!?!

너무 억울해서ㅜ기록을 남겨보려한다.

처음 푼 코드는 아래와같다.

from collections import deque

def solution(plans):
    answer = []
    tmp = []
    idx=0
    for name, start, playtime in plans:
        hours, minutes = map(int, start.split(":"))
        plans[idx][1] = hours * 60 + minutes
        plans[idx][2] = int(playtime)
        idx+=1
    
    plans = sorted(plans,key = lambda x: x[1])
    print(plans)
    
    for i in range(0, len(plans) - 1):
        if plans[i][1] + plans[i][2] > plans[i+1][1]:
            # 남은 시간(작업완료필요시간 - 현재까지작업한시간) 계산후 작업보류
            remaining_time = plans[i][2] - (plans[i+1][1] - plans[i][1])
            tmp.append([plans[i][0],remaining_time]) # 작업보류
        else:
            answer.append(plans[i][0])
    # 마지막 과제 끝내기
    answer.append(plans[-1][0])
    
    while len(tmp)!=0:
        name, remaining_time = tmp.pop()
        answer.append(name)
    
    
    return answer

 

바로 이조건....때문에 두시간순삭....

나는 만약 과제를 끝낸 시각에 새로 시작해야 되는 과제가있다면 새시작 과제를 우선적으로 진행하는구나~

라고만 이해했다. 그런데 정확히 "과제를 끝낸 시각"에 새로 시작해야 되는 과제가 있다면 새시작과제를 진행하고,아니면 디폴트로 잠시멈춰둔 과제를 진행하는것임...

 

즉 문제에서 과제를 끝냈을 때 잠시 멈춘 과제가 있다면 즉시 가장 최근에 멈춘 과제를 이어서 진행해야 한다. 하지만 위 코드에서는 모든 과제를 처리한 후에야 멈춰둔 과제들을 한 번에 처리한다.

 

 

예를 들어, 다음과 같은 테스트 케이스를 고려가능하다.
plans = [["A", "12:00", "50"], ["B", "12:20", "10"], ["C", "13:00", "10"]]
위 내 코드로 처리하면 결과는 ["B", "C", "A"]가 된다. 그러나 올바른 결과는 ["B", "A", "C"]입니다. 그 이유는 과제 B가 끝난 후 과제 C가 시작하기 전까지의 시간 동안 멈춰둔 과제 A를 이어서 진행할 수 있기 때문이다!!!

 

문제를 잘읽자...ㅠ...따라서 curr_time으로 현재를 추적해야한다..

def solution(plans):
    answer = []
    tmp = []
    idx=0
    for name, start, playtime in plans:
        hours, minutes = map(int, start.split(":"))
        plans[idx][1] = hours * 60 + minutes
        plans[idx][2] = int(playtime)
        idx+=1

    plans = sorted(plans,key = lambda x: x[1])

    for i in range(0, len(plans) - 1):
        current_end_time = plans[i][1] + plans[i][2]
        next_start_time = plans[i+1][1]

        if current_end_time > next_start_time:
            # 작업 보류
            remaining_time = current_end_time - next_start_time
            tmp.append([plans[i][0], remaining_time])
        else:
            # 현재 과제 완료
            answer.append(plans[i][0])
            # 남은 시간 동안 멈춘 과제 처리
            gap = next_start_time - current_end_time
            while tmp and gap > 0:
                name, remaining_time = tmp.pop()
                if remaining_time <= gap: # 남은시간이 gap이하면 작업완료가능
                    gap -= remaining_time
                    answer.append(name)
                else: # gap보다크면 일부만 진행
                    tmp.append([name, remaining_time - gap])
                    break

    # 마지막 과제 처리
    answer.append(plans[-1][0])
    # 남은 멈춘 과제 처리
    while tmp:
        name, remaining_time = tmp.pop()
        answer.append(name)

    return answer

 

자바풀이는 아래와같다

import java.util.*;

class Solution {
    public String[] solution(String[][] plans) {
        List<Plan> li = new ArrayList<>();
        Deque<PausedTask> tmp = new ArrayDeque<>();
        List<String> ans = new ArrayList<>();
        for (String[] plan : plans) {
            String[] split = plan[1].split(":");
            int start = Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
            int playTime = Integer.parseInt(plan[2]);
            li.add(new Plan(plan[0], start, playTime));
        }
        
        li.sort((o1,o2) -> o1.start - o2.start); // 오름차순 정렬
        
        for (int i = 0; i < li.size() - 1; i++) {
            String currentName = li.get(i).name;
            int start = li.get(i).start;
            int playTime = li.get(i).playTime;
            int nextStartTime = li.get(i + 1).start;
            int currentEndTime = start + playTime;
            
            if (currentEndTime > nextStartTime) {
                // 현재 과제가 다음 과제 시작 전에 끝나지 않으면 작업 보류
                int remainingTime = currentEndTime - nextStartTime;
                tmp.push(new PausedTask(currentName, remainingTime));
            } else { // 현재 과제가 다음 과제 시작 전 끝날 때
                ans.add(currentName);
                
                int gap = nextStartTime - currentEndTime;
                while (!tmp.isEmpty() && gap > 0) {
                    PausedTask pausedTask = tmp.pop(); // 가장 최근 멈춘 작업
                    if (pausedTask.remainingTime <= gap) { // 남은시간 내 작업완료
                        gap -= pausedTask.remainingTime;
                        ans.add(pausedTask.name);
                    } else { // 남은 시간이 gap보다 크면 일부만 진행
                        pausedTask.remainingTime -= gap;
                        tmp.push(pausedTask);
                        break;
                    }
                }
            }
            
        }
        
        // 마지막 과제처리
        ans.add(li.get(li.size()-1).name);
        
        // 남은 과제들 처리
        while (!tmp.isEmpty()) {
            PausedTask pausedTask = tmp.pop();
            ans.add(pausedTask.name);
        }
        
        return ans.toArray(new String[0]);
    }
    static class Plan {
        String name;
        int start;
        int playTime;
        
        Plan(String name, int start, int playTime) {
            this.name = name;
            this.start = start;
            this.playTime = playTime;
        }
    }
    static class PausedTask {
        String name;
        int remainingTime;
        
        public PausedTask(String name, int remainingTime) {
            this.name = name;
            this.remainingTime = remainingTime;
        }
    }
}