[프로그래머스] 과제 진행하기 (Java 풀이)

문제 링크

프로그래머스

서론

이 문제는 프로그래머스 레벨 2 문제로, 자신이 어느 정도 문제 해결 능력이 있다고 생각하면, 한 번쯤 풀어볼만한 문제입니다.스택뿐만 아니라 정렬(객체 정렬), 선점 스케줄링도 공부해볼 수 있어서 많은 공부가 되는 문제입니다.

사실 문제를 풀 때, 스케줄링이라고 해서 당연히 큐를 이용하는 문제인 줄 알았는데, 두번째 예시를 보고 스택임을 알아차렸습니다...
만만하게 봤다가 예외처리와 흐름정리에 4시간 넘게(...) 잡아먹어버렸습니다...💦
여러가지 시행착오를 거치다가, 아래 코드를 제출하니 풀렸습니다!

풀이 요약

선점 스케줄링과 스택을 이해하고 있으면 쉽게 풀 수 있습니다.
문제에서 주어진 대로 차근차근 생각해나가면 됩니다.
제가 풀이한 과정은 다음과 같습니다.

1. 입력된 문자열 배열을 시간에 따라 오름차순으로 정렬
2. 1분씩 늘려가며 스택을 이용해서 스케줄링 진행
3. 스케쥴링 안에서는 문제에서 주어진 대로 분기 수행

자세한 풀이

쓰고 나니까 너무 기네요.

1. Plan 객체를 새로 만들어서 ArrayList 배열에 넣어 정렬합니다.
   Plan 객체에는 주어진 입력에서 문자열로 주어졌던 시간과 분을 분리해서 정수로 저장하도록 했습니다.
   정렬은 다음 코드와 같이 시간(h)과 분(m)을 비교해서 a가 크면 1, b가 크면 -1을 반환하도록 했습니다.

private static int comparePlan(Plan a, Plan b) {
    if (a.h > b.h) return 1;
    else if (a.h < b.h) return -1;
    else {
        if (a.m > b.m) return 1;
        else if (a.m < b.m) return -1;
    }
    return 0;
}

2. 분 단위 시간(t)을 기준으로 반복문을 돌려 스케쥴링을 진행합니다.
   문제에서 주어진 시간의 제한이 00:00 ~ 23:59 이어서, 60*24 = 1440 번의 반복만 진행하면 됩니다.
   2-1. 현재 수행하고 있는 과제(이하 proc)가 없고, 새로 수행해야 할 과제가 존재한다면(checkNewTime),
   proc 변수에 지금 시간에 수행할 과제를 넣습니다.
   2-2. proc가 있으면 proc의 작업수행시간(play)를 시간이 갈 때마다 줄여나갑니다.
3. proc의 작업 수행 시간(play)가 아직 있는데 새로 수행할 과제가 있으면,
   스택에 현재 과제를 넣고 새로 수행할 과제를 proc에 넣습니다.
4. proc의 작업 수행 시간(play)가 끝나면, 문제에서 주어진 내용에 따라서 다음과 같이 진행합니다.
   4-1. 결과 배열에 proc를 넣고 proc를 비웁니다(proc = null)
   4-2. 스택이 비어있지 않으면, 스택에 있는 과제를 현재 과제로 넣습니다.
   4-3. 새로 수행할 과제가 있으면, (4-2를 진행했을 경우 스택을 원래대로 돌리고)4-4. 인덱스(idx)가 주어진 과제의 길이와 같으면 더 이상 새롭게 수행할 과제가 없다는 뜻이므로 반복문을 끝냅니다.
5. 혹시나 proc와 stack에 남아있는 과제가 있으면 추가해 넣습니다.

풀이 코드

import java.util.*;

class Solution {

  static class Plan {
    String name;
    int h, m;
    int play;
    Plan(String name, int h, int m, int play) {
      this.name = name;
      this.h = h;
      this.m = m;
      this.play = play;
    }
  }

  private static int comparePlan(Plan a, Plan b) {
    if (a.h > b.h) return 1;
    else if (a.h < b.h) return -1;
    else {
      if  (a.m > b.m) return 1;
      else if (a.m < b.m) return -1;
    }
    return 0;
  }

    public String[] solution(String[][] plans) {
        ArrayList<Plan> planList = new ArrayList<>();
        ArrayList<String> answer = new ArrayList<>();

        for (int i = 0; i < plans.length; i++) {
          String[] time = plans[i][1].split(":");
          planList.add(new Plan(plans[i][0],
              Integer.parseInt(time[0]),
              Integer.parseInt(time[1]),
              Integer.parseInt(plans[i][2])));
        }
        planList.sort(Solution::comparePlan);
        int idx = 0;
        int t = -1;
        Stack<Plan> stack = new Stack<>();
        Plan proc = null;
        while (t++ < (60 * 24)) {
          int h = t / 60, m = t % 60;

          Plan plan = null;
          boolean checkNewTime = false;
          if (idx < plans.length) {
            plan = planList.get(idx);
            checkNewTime = plan.h == h && plan.m == m;
          }
          if (proc != null) {
            proc.play--;
            if (proc.play <= 0) {
              answer.add(proc.name);
              proc = null;
              if (idx == plans.length) break;
              else if (!stack.isEmpty()) {
                proc = stack.pop();
              }
            }
            if (checkNewTime) {
              if (proc != null) stack.push(proc);
              proc = plan;
              idx++;
            }
          } else if (checkNewTime) {
            proc = plan;
            idx++;
          }
        }
        if (proc != null) {
          answer.add(proc.name);
        }
        while (!stack.isEmpty()) {
          answer.add(stack.pop().name);
        }

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

배운 점

1. 사용자 지정 정렬 함수(compare)에 대해서 다시 공부하게 됐습니다.

사용자 지정 정렬 함수를 만들 때, 항상 반환 값이 헷갈렸는데, 이번 기회에 다시 공부하게 됐습니다.

// 오름차순 예시
private static int compare(Integer a, Integer b) {
    if (a > b) return 1;
    else if (a < b) return -1;
    return 0; // a == b
}

2. 선점 스케줄링에 대해서 다시 공부하게 됐습니다.

간단하게 설명드리자면, 선점 스케줄링은 현재 한 프로세스가 수행 중일 때 다른 프로세스가 수행 중인 프로세스의 자원을 점유할 수 있는 방식입니다.
쉽게 말해서 누가 일하고 있는데 중간에 끼어들 수 있는 스케줄링 방법입니다.
선점 스케줄링은 크게 SRT, 라운드로빈, 다단계 큐 스케줄링이 있다는 것도 다시 알고 갔습니다.

 

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!