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

https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

코딩테스트 연습 > 연습문제 > 과제 진행하기 

 

문제 접근

스택/큐 + 정렬 문제!!

 

과제는 3가지 정보가 있다.

1. 과제 이름

2. 시작 시간

3. 걸리는 시간 

 

해당 정보를 편하게 사용하기 위해 Task Class 생성 

쉽게 저장을 하기 위해서 Task 생성자 생성  

static class Task {
    public String name;    // 이름
    public int startTime;  // 시작 시간
    public int leftTime;   // 걸리는 시간 

    public Task(String name, int startTime, int leftTime){
        this.name = name;
        this.startTime = startTime;
        this.leftTime = leftTime;
    }
}

 

시작 시간은 hh:mm 문자열 형태로 들어온다. 

int형 변환 메서드 calculate

// 시간:분 -> 분 
public static int calculate(String input){
    String [] split = input.split(":");
    return (Integer.parseInt(split[0]) * 60) + Integer.parseInt(split[1]);
}

 

해당 정보 list에 넣기

중요! 왜 PriorityQueue를 사용하지 않는 것인가 

우선순위 큐는 ADT이다. ADT는 추상 자료 구조라는 뜻인데 실제 동작을 구현하지 않는 설명만 있는 자료구조이다.

우선순위 큐의 실제 구현은 힙이다. 힙은 삽입/삭제 시 매번 O(logN)이 걸린다.

우리는 과제 시작 시간이 빠른 순서대로 정렬해둔 데이터가 필요한데 

이건 리스트에 다 넣고 한 번에 정렬을 해도 같은 결과이다. 

실제로 백준이나 프로그래머스에서 이런 차이로 시간 초과가 발생한 적이 많다. 

그러니 단 한 번의 정렬이 필요하면 리스트를 사용하자. 

ArrayList<Task> list = new ArrayList<>();
for(int i = 0; i < plans.length; i++){
    int time = calculate(plans[i][1]);
    list.add(new Task(plans[i][0], time, Integer.parseInt(plans[i][2])));
}

// sort 시작 시간이 빠른 순서대로 
Collections.sort(list, (o1, o2) -> {
   return o1.startTime - o2.startTime;
});

핵심 로직  설명 

 

현재 리스트에는 과제 시작 시간이 빠른 순서대로 정렬되어 있다.

time = 0 설정 

 

for문 진행

 

리스트에서 과제를 하나 꺼낸다.

소비 가능한 시간 = (현재 과제 시작 시간 - time(진행된 시간))

 

stack = 과제를 진행하다가 멈춘 과제들 (문제에서는 가장 최근에 멈춘 과제를 진행하기를 원한다 is stack.peek)

 

stack에 과제가 있고 소비 가능한 시간이 0이상 이면 계속 진행한다. 

 

2가지 case 

 

1. 과제를 해결하기에 필요한 시간이 소비 가능한 시간보다 크거나 같은 경우 

 

과제를 해결하기에 필요한 시간 = 과제를 해결하기에 필요한 시간 - 소비 가능한 시간;

 

더이상 소비 가능한 시간은 없다 time = 0;

 

과제를 해결하기에 필요한 시간  ==  0 ? 

1 - 1 true이면 해당 과제는 끝났으니 해당 과제 이름을 큐에 넣는다. 

1 - 2 false이면 다시 스택에 넣는다. 

 

2. 1번의 반대 case

 

소비 가능한 시간을 스택에서 꺼낸 과제를 해결하기에 필요한 시간 만큼 빼준다. 

해당 과제 이름을 큐에 넣는다. 

 

 

진행된 시간(time) = 현재 과제 시작 시간

stack에 현재 과제를 넣는다. 

 

int time = 0;
for(int i = 0; i < list.size(); i++){
    Task cur = list.get(i);

    int time_slice = cur.startTime - time;

    while(!stack.isEmpty() && time_slice > 0){
        Task temp = stack.pop();

        if(temp.leftTime >= time_slice){
            temp.leftTime -= time_slice;
            time_slice = 0;

            if(temp.leftTime != 0){
                stack.push(temp);
                continue;
            }

            answer.add(temp.name);
        }
        else{
            time_slice -= temp.leftTime;
            answer.add(temp.name);
        }
    }
    stack.add(cur);
    time = cur.startTime;
}

 

먼저 과제가 끝난 순서대로 큐에서 end 배열에 넣어주고

그런 다음 stack에서 꺼내 배열에 넣어준다. 

 

문제에서는 항상 마지막에 멈춘 과제부터 진행하기를 원한다. 

 

전체 코드

import java.util.*;
class Solution {
    
    static class Task {
        public String name; 
        public int startTime;
        public int leftTime;
        
        public Task(String name, int startTime, int leftTime){
            this.name = name;
            this.startTime = startTime;
            this.leftTime = leftTime;
        }
    }
    
    // 과제가 끝난 순서 
    static Queue<String> answer = new LinkedList<>();
    
    // 진행중이던 과제 보관 
    static Stack<Task> stack = new Stack<>();
    
    public String[] solution(String[][] plans) {
        ArrayList<Task> list = new ArrayList<>();
        for(int i = 0; i < plans.length; i++){
            int time = calculate(plans[i][1]);
            list.add(new Task(plans[i][0], time, Integer.parseInt(plans[i][2])));
        }
        
        // sort 시작 시간이 빠른 순서대로 
        Collections.sort(list, (o1, o2) -> {
           return o1.startTime - o2.startTime;
        });
        
        int time = 0;
        for(int i = 0; i < list.size(); i++){
            Task cur = list.get(i);
            
            int time_slice = cur.startTime - time;
            
            while(!stack.isEmpty() && time_slice > 0){
                Task temp = stack.pop();
                
                if(temp.leftTime >= time_slice){
                    temp.leftTime -= time_slice;
                    time_slice = 0;
                    
                    if(temp.leftTime != 0){
                        stack.push(temp);
                        continue;
                    }
                    
                    answer.add(temp.name);
                }
                else{
                    time_slice -= temp.leftTime;
                    answer.add(temp.name);
                }
            }
            stack.add(cur);
            time = cur.startTime;
        }
        
        String [] end = new String [list.size()];
        int cnt = 0;
        
        while(!answer.isEmpty()){
            end[cnt++] = answer.poll();
        }
        
        while(!stack.isEmpty()){
            end[cnt++] = stack.pop().name; 
        }
           
        return end;
        
    }
    // 시간:분 -> 분 
    public static int calculate(String input){
        String [] split = input.split(":");
        return (Integer.parseInt(split[0]) * 60) + Integer.parseInt(split[1]);
    }   
}