과제 진행하기

 

진짜 별 난리를 치고 허우적거리다 겨우 푼 문제.

안 풀려서 미루고 미루다가 거진 6개월만에 풀었지 싶다..

 

---

 

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/176962

프로그래머스

 

---

 

Problem

간단하게 과제 더미가 있고, 완벽주의자 J의 성향을 가진 '루' 라는 친구가 수많은 과제를 어떤 순서로 마치는지 맞혀보라고 골치를 썩이는 문제이다.

 

 

각 과제는 문자열 배열에 ["과제 이름", "과제 시작 시간", "과제가 걸리는 시간"] 으로 정보가 담기며,

전체 과제는 따라서 2차원 배열에 주어진다.

각 데이터에 규칙이 존재하는데, 중요한 정보만 꼽으면 다음과 같다.

 

1. 과제 이름은 중복되지 않는다.

2. 과제 시작 시간은 "HH:mm" 포맷으로 주어지며, "00:00" ~ "23:59" 사이이다.

3. 과제가 걸리는 시간은 1 이상, 100 이하이다. (단위는 minute)

 

 

이제 과제를 푸는 규칙을 살펴보자. 역시 중요한 정보만 나열하면 다음과 같다.

이해를 위해 미리 설명하면, 과제에는 '새로운' 과제와 '하고 있던' 과제로 나뉜다.

'새로운' - 과제를 1분도 진행하지 않은, 계획된 시간이 되지 않은 과제

'하고 있던' - 1분이라도 진행했던, 현재 시점 계획된 시간이 지난 과제이며, 과제 시간이 남은 과제

 

1. '새로운' 과제는 주어진 시간에 무조건 시작해야 한다.

2. 과제를 진행하다가 다른 '새로운' 과제가 할 시간이 되면, '하고 있던' 과제를 잠시 냅두고 '새로운' 과제를 시작한다.

3. 더이상 진행할 과제가 없으면 (시간이 뜨면), '하고 있던' 남은 과제를 진행한다.

4. '하고 있던' 과제들이 많다면, 가장 최근에 하던 '하고 있던' 과제부터 진행한다.

5. 과제가 걸리는 시간을 모두 사용했다면 해당 과제는 끝마친 것으로 간주한다.

 

 

그냥 쉽게 설명하면,

과제 시작은 무조건 계획대로 진행하되,

다음 계획이 되면 하고 있던 건 잠시 냅두고,

계획대로 진행하다 뜨는 시간이 있다면 잠시 냅뒀던 과제를 최근 순서로 진행한다는 의미이다.

 

과제 간의 우선 순위를 표현하면 다음과 같다. ( A > B 라면 A 가 더 높은 우선순위를 갖는다는 의미 )

 

• (계획 시간이) 빠른 '새로운' 과제 > 느린 '새로운' 과제
  ex. 00:00 '새로운' > 00:01 '새로운'
  
  
• '새로운' 과제 > '하고 있던' 과제
  ex. '새로운' A 과제가 00:00 부터 10분 간 진행해야 한다면, 00:01 부터 A 는 '하고 있던' 과제가 되며,
       '새로운' B 과제가 00:05 부터 진행해야 한다면, 00:05 부터는 A 를 보류하고 B 를 진행.
  
  
• (현재 시간 시점으로) 최근 '하고 있던' 과제 > 이전에 '하고 있던' 과제
  ex. '하고 있던' A 과제가 10분 전에 중단 되었었고, '하고 있던' B 과제가 5분 전에 중단 되었다면,
      시간이 남는 시점에서 B -> A 순으로 진행.

 
 

Idea

자료구조에 익숙하다면 설명만으로 과제의 종류에 따라 다른 자료구조의 형태가 생각날 것이다.

 

'새로운' 과제의 경우는 시간에 따라 순차로 진행되기에 Queue

'하고 있던' 과제의 경우는, 가장 최근 멈춘 자료부터 시작하므로 Stack

을 떠올릴 수 있다.

 

즉, 각 과제를 시작 시간 순으로 정렬하여 Queue 에 전부 넣는다면

Queue 는 선회하며 새로운 과제를 순차적으로 poll 할 것이고,

특정 과제 진행 중에 다른 새로운 과제를 시작할 시간이 되어 잠시 보류해야 할 과제를 Stack 에 넣는다면

시간이 빌 때마다 Stack 에서 pop 하여 가장 최근의 보류 과제를 진행할 수 있다.

 

직관적인 예시는 다음과 같다.

 

 

 

 

 

Solution

나의 경우 앞선 예시와 같이 Stack, Queue 를 준비해놓고 진행했다.

이때 00:00 ~ 23:59 를 while 문으로 각 분을 체크하며 순간순간 이벤트를 처리하기에는 너무 비효율적이므로

각각의 시간을 저장하며, 앞서 설명했던 우선순위에 따라 과제를 저장하고 추출하도록 코드를 작성했다.

 

먼저 가장 높은 우선순위는 Queue 의 첫 과제 (poll) 이다. 

어떤 과제도 시작 시간이 된 과제보다 높은 우선순위를 가질 순 없다.

이 말은 결국 [이전에 수행하던 '새로운' 과제 시작 시간 ~ 다음에 수행될 '새로운' 과제 시작 시간] 사이에서 모든 이벤트는 일어난다는 의미이다.

따라서, Queue 에서 순차적으로 과제를 하나씩 꺼내어, 일어날 수 있는 경우의 수를 처리하는 식으로 진행해야 한다.

 

 

이때 새로운 과제가 Queue 에서 poll 됐다면, 일어날 수 있는 경우의 수는 다음과 같다.

 

- 이전에 진행 중이던 과제가 아직 안 끝남

- 이전 과제는 이미 끝났고, 끝남과 동시에 새로운 과제 시작

- 이전 과제는 이미 끝났고, 이전 과제 끝 시간 ~ 지금 과제 시작 시간 사이에 남는 시간이 있음

 

 

각각의 경우는 다음과 같이 처리해야 한다.

 

- 이전에 진행 중이던 과제가 아직 안 끝남

: 진행 중이던 과제를 남은 과제 시간과 함께 Stack 에 저장

 

- 이전 과제는 이미 끝났고, 끝남과 동시에 새로운 과제 시작

: 이전 과제를 정답 배열에 저장하고, 새로운 과제 시작

 

- 이전 과제는 이미 끝났고, 이전 과제 끝 시간 ~ 지금 과제 시작 시간 사이에 남는 시간이 있음

: 이전 과제 끝 시간 ~ 지금 과제 시작 시간 사이에 남는 시간만큼 Stack 의 과제 진행

 

 

이렇게 과제 간 사이의 공백 시간이 중요하므로,

Queue 에서 poll 한 과제 ~ Queue 에서 다음 poll 할 과제 (peek) 사이의 시간을 계산하여 알고리즘을 처리했다.

각 경우에 따른 알고리즘은 다음과 같다.

 

- 현재 과제 (poll) 가 다음 과제 (peek) 시작 시간보다 늦게 끝남

: 현재 과제의 남은 시간을 [다음 과제 시작 시간 - 현재 시간] 만큼 차감하고, Stack 에 저장

 

- 현재 과제 (poll) 가 다음 과제 (peek) 시작 시간과 동일

: 현재 과제를 정답 배열에 저장

 

- 현재 과제 (poll) 가 다음 과제 (peek) 시작 시간보다 일찍 끝남

: [다음 과제 시작 시간 - 현재 과제 끝남 시간] 을 계산하여, 남은 시간만큼 Stack 의 과제를 순차 진행

 
 

Code (Queue, Stack)

Queue 에서 시작 시간 기준 정렬된 과제들을 하나씩 poll 하며,

각 시간을 계산 후 우선순위에 맞게 이벤트를 처리한 코드는 다음과 같다.

 

import java.util.*;
import java.time.*;
import java.time.format.DateTimeFormatter;
import java.time.format.DateTimeFormatterBuilder;
import java.time.temporal.ChronoField;
class Solution {
	
	class HomeWork {
		String name;
		LocalDateTime start;
		long remainSec;
		
		HomeWork(String name, LocalDateTime start, long remainSec) {
			this.name = name;
			this.start = start;
			this.remainSec = remainSec;
		}
	}
	
	
    public String[] solution(String[][] plans) {
    	
    	String[] answer = new String[plans.length];
    	
    	
    	// plans 정렬
    	Arrays.sort(plans, (x,y) -> x[1].compareTo(y[1]));
    	
    	
    	// Queue 에 삽입
    	Queue<HomeWork> hwQue = new LinkedList<>();
        DateTimeFormatter formatter = new DateTimeFormatterBuilder()
    	        .append(DateTimeFormatter.ISO_LOCAL_TIME)
    	        .parseDefaulting(ChronoField.EPOCH_DAY, 0)
    	        .toFormatter();
        
    	for(String[] plan : plans) {
    		hwQue.offer(new HomeWork(
    				plan[0],
    				LocalDateTime.parse(plan[1], formatter),
    				Duration.ofMinutes(Long.parseLong(plan[2])).getSeconds()
				));
    	}
    	
    	
    	// 알고리즘
    	Stack<HomeWork> hwStack = new Stack<>();
    	
    	int idx = 0;
    	LocalDateTime curTime = hwQue.peek().start; // 이전 과제가 끝난 시간
    	HomeWork curHw = null;
    	HomeWork temp = null;
    	
    	while(idx < answer.length && !hwQue.isEmpty()) {
    		
            // 현재 과제
    		curHw = hwQue.poll();
    		
            // 이전 과제가 끝난 시간 (curTime) 과 현재 과제의 시작 시간 (start) 간격을 계산하여,
            // 남는 시간이 있고 stack 에도 처리해야 할 과제가 있다면 남는 시간만큼 과제 진행
    		while(!hwStack.isEmpty() && curTime.isBefore(curHw.start)) {
    			
    			temp = hwStack.pop();
    			
                // 남는 시간동안 진행하던 과제가, 현재 과제 시작 시간보다 늦게 끝난다면, stack 에 저장
                // 아니라면 과제가 끝난 것이므로 정답에 저장
    			if(curTime.plusSeconds(temp.remainSec).isAfter(curHw.start)) {
    				temp.remainSec -= Duration.between(curTime, curHw.start).getSeconds();
    				hwStack.push(temp);
    				break;
    			}else {
    				answer[idx++] = temp.name;
    				curTime = curTime.plusSeconds(temp.remainSec);
    			}
    		}
    		
    		
            // 현재 시간은 현재 과제의 시작 시간으로 설정
    		curTime = curHw.start;
    		
            // 현재 과제가 다음 과제의 시작 시간보다 늦게 끝난다면, 진행할 시간만큼 차감하고 stack 에 저장
            // 아니라면 과제가 끝날 것이므로 정답에 저장
    		if(!hwQue.isEmpty() && curTime.plusSeconds(curHw.remainSec).isAfter(hwQue.peek().start)) {
    			curHw.remainSec -= Duration.between(curTime, hwQue.peek().start).getSeconds();
    			hwStack.push(curHw);
    			curTime = hwQue.peek().start;
    		}else {
    			answer[idx++] = curHw.name;
    			curTime = curTime.plusSeconds(curHw.remainSec);
    		}
    	}
    	
        
        // 추가로 새로운 과제(Queue)는 모두 마쳤으나, Stack 에 과제가 남아 있을 수 있으므로 처리
    	while(!hwStack.isEmpty()) {
    		answer[idx++] = hwStack.pop().name;
    	}
    	
    	
    	return answer;
    }
}

 

 

나의 경우 Duration 을 통해 두 시간 사이의 차이를 계산했고,

계산의 편의를 위해 시간 관련을 LocalDateTime 및 분 (minute) 단위를 초 (second) 단위로 바꾸어 계산을 진행했다.

 

추가로, 최초의 로직에서는 과제 시작 시간을 LocalTime 을 통해 진행했었는데,

계속 통과가 안 되어 확인해보니 23:59 이후 진행되는 과제들은 HH:mm 으로의 비교에서 오답을 내게 됐었다.

 

LocalTime 을 활용했을 때의 오답 예시

 

이는 [현재 과제 시작 시간 + 남은 시간] 이 00:00 을 넘어가면서,

원래라면 23:59 보다 늦게 끝날 것으로 판단하여야 하지만 00:00 < 23:59 으로 비교하게 되어

올바른 정답을 내지 못하는 것으로 보인다.

해당 문제는 LocalTime -> LocalDateTime 으로 수정하자 해결되었으며,

해당 문제 해결 이전 정답률이 40 점 대인 것으로 보아 비중 있게 생각해야 할 이슈로 확인된다.

 

코드에서는 배열을 시작 시간 기준으로 정렬 후 Queue 에 삽입했는데,

생각해보니 PriorityQueue 로 과제를 삽입했다면 시간을 더 줄일 수 있을 것 같다.

이는 추후 적용하여 수정하도록 하겠다.

 
 

End

LocalDateTime 의 문제 말고도 로직적인 문제로 인해 여러 난항을 겪었던 문제다.코딩 테스트에 주로 출제하는 유형인만큼 잘 풀고 실수가 없어야 하는데.. 큰일이다.세세한 알고리즘 작성을 목표로 공부하자.