[프로그래머스]Lv2.파헤치기 자바(Java) 과제 진행하기

Wang_Seok_Hyeon·2023년 4월 2일
1
post-thumbnail

프로그래머스의 Lv2. 과제 진행하기
23-03-30에 나온 문제로 구현과 정렬에 관한 문제로 크게 어려운 문제라기 보단,
얼마나 기본을 잘 익혔느냐 하는 걸 확인해 볼 수 있는 문제였던 것 같다.

문제의 이해는 과제를 진행하는데 있어,

과목명, 시작시간과, 소요시간이 담긴 String[][] plans가 제공되며,
이 다음 과목의 시작시간이 되면 종료되지 않았더라도 멈추고 소요시간의 감소가 발생한다.

그리고, 다음 과제를 진행하는데 있어, 소요시간이 빨리 끝난 경우
(가령 12시 10분에 시작한 과제가 12시 20분에 끝나고 다음 과제의 시작은 12시 30분인 경우)

만약 멈췄던 과제가 있다면, 가장 최근에 멈춘 과제를 다시 시작한다.는 부분들이 핵심을 이루는 구현 부분이 된다.

우선 아래의 코드를 보자.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

class Assignment implements Comparable<Assignment> {
    String subject;
    int start;
    int time;

    public Assignment(String subject, int start, int time) {
        this.subject = subject;
        this.start = start;
        this.time = time;
    }
    
     public Assignment(String subject, int time) {
        this.subject = subject;
        this.time = time;
    }

    @Override
    public int compareTo(Assignment o) {
        return this.start - o.start;
    }
}

class Solution {
    public String[] solution(String[][] plans) {
        List<Assignment> assignments = new ArrayList<>();
        for (String[] plan : plans) {
            String subject = plan[0];
            String[] split = plan[1].split(":");
            int start = Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
            int time = Integer.parseInt(plan[2]);
            assignments.add(new Assignment(subject, start, time));
        }
        Collections.sort(assignments);

        Stack<Assignment> stack = new Stack<>();
        List<String> answer = new ArrayList<>();
        for (int i = 0; i < assignments.size(); i++) {
           if(i == assignments.size()-1){//마지막인 경우
               answer.add(assignments.get(i).subject);
               break;
           }
            int current = assignments.get(i).start + assignments.get(i).time;
            int next = assignments.get(i + 1).start;
            int differ = next - current;
            if(differ < 0){//끝나지 않은 것. stack에 추가.
                stack.push(new Assignment(assignments.get(i).subject,Math.abs(differ)));
            }else{//충분히 소요되는 것. 두 가지로 나뉨.
                    answer.add(assignments.get(i).subject);
                if(differ > 0){//0보다 큰 경우,
                    while(!stack.isEmpty()&&differ > 0){
                        if(stack.peek().time <= differ){
                            answer.add(stack.peek().subject);
                            differ-=stack.pop().time;
                        }else{
                            //differ가 더 작은 경우
                            Assignment tmp = stack.pop();
                            stack.push(new Assignment(tmp.subject, tmp.time-differ));
                            break;//종료조건
                        }
                    }
                }
            }
        }
            while(!stack.isEmpty())
                answer.add(stack.pop().subject);
                       
        return answer.toArray(new String[0]);
    }
}

위의 코드를 크게 2가지로 나눈다면, 위에서 언급한 정렬과 구현에 관한 문제라는 요소 그대로,
1. 정렬
2. 구현에 관한 내용일 것이다.

하나씩 차근차근 이야기 해 보자.

  1. 정렬
    정렬의 경우 생성자를 2개를 두었다. 이유는 시작시간의 경우 최초에만 필요하고, 이후에는 소요시간만이 stack에서 가치가 있기 때문이다.
    implements Comparator를 통해,
    구현체인 public int compareTo(Assignment o){}로 정렬의 기준을 제공했다.

    class Assignment implements Comparable<Assignment> {
      String subject;
      int start;
      int time;
    
      public Assignment(String subject, int start, int time) {
          this.subject = subject;
          this.start = start;
          this.time = time;
      }
      
       public Assignment(String subject, int time) {
          this.subject = subject;
          this.time = time;
      }
    
      @Override
      public int compareTo(Assignment o) {
          return this.start - o.start;
      }
    }
  
  이후에는 구현을 위한 본 문제의 부분을 볼 필요가 있다. 여기서 기본적으로 값의 정렬을 맡아 줄 부분과
  구현에 관한 로직 2가지가 주요한 부분이다.
  
  1. 정렬에 관한 부분
  
List<Assignment> assignments = new ArrayList<>();
    for (String[] plan : plans) {
        String subject = plan[0];
        String[] split = plan[1].split(":");
        int start = Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
        int time = Integer.parseInt(plan[2]);
        assignments.add(new Assignment(subject, start, time));
    }
    Collections.sort(assignments);
위의 내용을 통해 알 수 있지만, 시간의 경우, 모두 분으로 환산한 정수 값으로 계산한 것을 볼 수 있다.
  이때, 시간을 분리해주는 기준을 시:분 사이에 있는 ":"를 기준으로 해주었으며, 
  소요시간에 해당 내용은 크게 어려운 부분은 아니었다. 
  마지막으로 Collections.sort(assignments)가 있는데,
  해당 로직은 앞서 언급한 정렬을 위한 클래스에 정의되어 있는 기준에 따라, 
  시작 시간의 오름차순으로 정렬이 이루어지게 된다.
  
  2. 구현에 관한 부분
  
Stack<Assignment> stack = new Stack<>();
        List<String> answer = new ArrayList<>();
        for (int i = 0; i < assignments.size(); i++) {
           if(i == assignments.size()-1){//마지막인 경우
               answer.add(assignments.get(i).subject);
               break;
           }
            int current = assignments.get(i).start + assignments.get(i).time;
            int next = assignments.get(i + 1).start;
            int differ = next - current;
            if(differ < 0){//끝나지 않은 것. stack에 추가.
                stack.push(new Assignment(assignments.get(i).subject,Math.abs(differ)));
            }else{//충분히 소요되는 것. 두 가지로 나뉨.
                    answer.add(assignments.get(i).subject);
                if(differ > 0){//0보다 큰 경우,
                    while(!stack.isEmpty()&&differ > 0){
                        if(stack.peek().time <= differ){
                            answer.add(stack.peek().subject);
                            differ-=stack.pop().time;
                        }else{
                            //differ가 더 작은 경우
                            Assignment tmp = stack.pop();
                            stack.push(new Assignment(tmp.subject, tmp.time-differ));
                            break;//종료조건
                        }
                    }
                }
            }
        }
            while(!stack.isEmpty())
                answer.add(stack.pop().subject);

위의 내용이 관련한 부분을 전체 구현했다고 생각되는 요소들이다.
1. 가장 최근에 멈춘 것을 확인하기 위한 stack
이때, stack에 들어갈 요소는 과목명과 남은 소요시간으로 만들 예정.
List answer 과목명을 담을 List로 리턴 값은 연습 차원에서 stream 식을 활용.

구현부에 for문을 하나만 사용 했지만, 해당 for문에 걸리는 조건식이 많아서
나도 해당 조건식들을 정리하고 했는데, 해당 조건식의 핵심은 differ라는 변수다.

해당 differ는 최초의 정렬된 데이터를 바탕으로
현재시간과 소요시간을 더한 current 라는 변수와
다음 시작시간을 담을 next의 뺄셈으로 구성한다.
differ = next - current
여기서 differ의 값이 0보다 크냐, 작으냐를 기준으로 값을 만들 수 있다.
0보다 작다면, 끝나지 않는다는 것을 의미하기 때문에,
stack에 추가해 주는데 이때 과목명과 남은 소요시간을 넣어줄 수 있다.
이때 남은 시간은 differ의 절대값에 해당해서 Math.abs(differ)로 구현했다.

이후 differ >= 0 의 경우, answer에 넣어주고,
differ가 0보다 큰 상태에서 stack이 비어 있지 않다면, 남은 시간 사이에
과제를 할 수 있다는 의미이기 때문에 해당 부분을 처리해 준다.

해당 구현은
if(differ > 0)으로 시작해
while(!stack.isEmpty() && differ > 0) 으로 만들어 줬다.
둘 중 하나라도 만족하지 못하면 지속할 필요가 없기 때문에 위와 같이 구현했으며

만약, differ값이 stack의 peek한 time 값 보다 크면
answer에 들어가며, differ의 값을 조정해 준다.

이와 반대로 differ 값보다 stack.peek().time이 크면
answer에 들어갈 수 없다.
다만, differ만큼 소요시간을 줄여서 다시 stack에 넣어준다.
그리고 해당 while문을 빠져나가면 된다.

논리 구조 상으로 보면, for문은 i == assignments.size()-1까지 간다.
이는 list의 끝까지 간다는 말이고, 이렇게 두면 next 값을 구하는 과정에서
indexOfOutOfBounds가 발생하기 때문에,
마지막 과목이 시작하는 경우라면, 그 과목을 answer에 추가해 주고,
for문을 종료해줌으로써 해당 구현부의 큰 틀은 끝이난다.

이후, while문에 stack이 남아 있다면 최근에 멈췄던 순서대로,
answer에 과제를 끝내주는 과정을 구현하고
answer.stream().toArray(new String[0]);

으로 for문을 이용하거나 등의 과정을 생략했다.

재밌는 문제인 만큼 한 번 풀어보면 좋을 거 같다 :)

profile
하루 하루 즐겁게

0개의 댓글