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

1. 문제 정의 

조건

과제는 시작하기로 한 시작이 되면 시작한다(우선순위가 가장 높음.)

새로운 과제할 시각이 되면 기존에 진행하던 과제는 멈추고 새로운 과제를 실시함.

진행 중인 과제가 끝나고, 멈춘 과제가 있었을 경우 가장 최근에 멈춘 과제부터 진행.

과제가 끝나고, 새로 시작하는 과제와 멈춘과제가 있다면 새로시작하는 과제부터 진행(새로시작하는게 무조건 우선순위)

 

일 때 과목이 끝나는 순서를 배열로 리턴하는 것이 문제

 

input 데이터

[["과목1", "10:10", "30"],["과목2","11:00","80"]]

 

output 데이터

["과목1", "과목2"]

 

2. 내가 한 시도

 문제가 cpu에서 우선순위에 따라 task를 처리하는 모습과 굉장히 닮아 있다고 생각했다. 일단 먼저 생각난 것이 멈춘 과제가 있다면 가장 최근 과제 부터 시작해야 하기 때문에 스택을 사용하면 좀 더 효율적으로 로직을 작성할 수 있겠다고 생각했다.

 그리고 가장 최근 시각부터 시작을 해야하므로 시작시간을 기준으로 정렬이 필요하겠다고 생각했다. 그래서 2가지 생각을 바탕으로 코딩을 시작했고, 아래의 코드와 같은 결과가 나왔다.

 

3. 코드

import java.time.Duration;
import java.time.LocalTime;
import java.util.*;

/**
 * 프로그래머스 LV2
 * 연속된 부분 수열의 합
 * 풀이
 * 1. 기존과제 진행 도중 새 과제 시간이되면 기존과제는 정지, 새 과제 실행
 * 2. 과제 완료시 멈춘과제, 새 과제가 있다면 새 과제 실행
 * 3. 멈춘 과제는 가장 최근에 멈춘 것부터 다시 실행
 * 을 바탕으로 스택을 이용해서 구현.
 * 1. 시간별로 정렬하기
 * 2. 순회하면서 시간을 계산해주기
 * 3. 시간을 계산하면서 남은시간이 0이되면 배열에 과목 추가해주기.
 */
public class Solution {
    public static void main(String[] args) {
        String[] solution = solution(new String[][]{{"science", "12:40", "50"}, {"music", "12:20", "40"}, {"history", "14:00", "30"},{"computer", "12:30", "100"}});
        for (String s : solution) {
            System.out.println(s);
        }
    }


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

        Subject[] subjects = new Subject[plans.length];
        /*
         * 처음 받은 배열을 객체로 변환해서 subject 배열에 저장
         */
        for (int i = 0; i < plans.length; i++) {
            String[] plan = plans[i];
            subjects[i] = new Subject(plan[0], plan[1], plan[2]);
        }

        /*
         * 시간기준 오름차순 정렬
         */
        Arrays.sort(subjects, (o1, o2) -> o1.sortAsc(o2));

        /*
         * 완료가 안된 과목들을 넣어두는 곳.
         */
        Stack<Subject> notComplete = new Stack<>();

        /*
         * 현재 과목 시작시간과 다음 과목 시작시간을 비교하여 leftTime을 마이너스 시켜준다.
         */
        for (int i = 0; i < subjects.length - 1; i++) {
            Subject subject = subjects[i];
            Subject nextSubject = subjects[i + 1];

            LocalTime now = subject.getTime();
            LocalTime nextTime = nextSubject.getTime();
            Duration between = Duration.between(now, nextTime); // 시간차 구하기
            long result = subject.minusLeftMin(between.toMinutes()); // 시간차만큼 마이너스 시켜주기

            /*
             * 아직 lefttime이 남았을 경우 스택에 넣기
             */
            if (result > 0) {
                notComplete.push(subject);
            }
            /*
             *  과목이 무사히 끝났거나 시간이 더 남을 때에는 완료된 과목 출력해주고, 스택에서 미 완료된 과목 꺼내서 leftTime minus 시켜주기.
             */
            else if (result <= 0) {
                answer.add(subject.getName());
                while (result<0 && !notComplete.isEmpty()) {
                    result*=-1;
                    Subject pop = notComplete.pop();
                    result = pop.minusLeftMin(result);
                    if(pop.leftMin <= 0){
                        answer.add(pop.getName());
                    }else{
                        notComplete.push(pop);
                    }
                }
            }
        }
        /*
         * 마지막에 있는 과목은 무조건 완료이기 때문에 완료에 추가
         */
        answer.add(subjects[subjects.length-1].getName());
        /*
         * 그리고 아직 완료되지 않은 과목이 남아있다면 이것도 최근순으로 완료시켜줌.
         */
        while (!notComplete.isEmpty()){
            answer.add(notComplete.pop().getName());
        }


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

    static class Subject {
        private String name;
        private LocalTime time;
        private int leftMin;

        public Subject(String name, String time, String leftMin) {
            this.name = name;
            String[] split = time.split(":");
            this.time = LocalTime.of(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
            this.leftMin = Integer.parseInt(leftMin);
        }

        public String getName() {
            return name;
        }

        public LocalTime getTime() {
            return time;
        }

        public int getLeftMin() {
            return leftMin;
        }

        public long minusLeftMin(long min) {
            long answer = this.leftMin - min;
            this.leftMin -= min;
            return answer;
        }

        public int sortAsc(Subject subject){
            if(this.getTime().isBefore(subject.getTime())){
                return -1;
            }
            if (this.getTime().isAfter(subject.getTime())){
                return 1;
            }
            return 0;
        }
    }
}

 

4. 회고

 역시 시간을 다루는 건 귀찮은 일이다. 이번로직에선 LocalTime 클래스을 이용해 시간 계산을 했다. 다행히도 편리하게 진행할 수 있었다.

정렬과 스택을 이용하여 어렵지 않게 문제를 풀어낼 수 있었던 것 같다.

 

참조

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