[테코테코1.5 2-04] 과제는 끝나지 않아!

💡테코테코 시즌 1.5 2회 모임 off-site 문제 풀이입니다. (2025.01.19)

 

문제

 

출처: 백준 - 과제는 끝나지 않아!

 

내용

 

성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다.

1. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
2. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.
3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다.)

성애는 과제를 받자마자 이 과제가 몇 분이 걸릴지 정확하게 알 수 있고, 성애가 제출한 과제는 무조건 만점을 받는다.

성애는 이번 학기에 자기가 받을 과제 점수를 예상해보고 싶다. 하지만 과제 점수를 예상하는 지금도 과제가 추가되고 있기에 여유를 부릴 수가 없다. 여러분이 성애가 받을 과제 점수를 구해주자!

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

과제 class 만들어서 해보는 건 어떨까.

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
00:00	00:35	35분

 

문제 분석

 

제약 사항 파악 & 입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

 

첫째 줄에 이번 학기가 몇 분인지를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

두번째 줄부터 N줄 동안은 학기가 시작하고 N분째에 주어진 과제의 정보가 아래의 두 경우 중 하나로 주어진다.

• 1 A T: 과제의 만점은 A점이고, 성애가 이 과제를 해결하는데 T분이 걸린다. A와 T는 모두 정수이다. (1 ≤ A ≤ 100, 1 ≤ T ≤ 1,000,000)
• 0: 해당 시점에는 과제가 주어지지 않았다.

3
1 100 3
0
0

 

성애가 받을 과제 점수를 출력한다.

100

• 1분째: 100점짜리 과제 1이 주어지고 이 과제를 하는데 3분이 걸린다. 과제를 받자마자 시작했으므로 과제 1이 끝나는데는 이제 2분 남았다.
• 2분째: 새로운 과제가 주어지지 않았으므로 과제 1을 이어서 한다.
• 3분째: 새로운 과제가 주어지지 않았으므로 과제 1을 이어서 한다. 이 시점에 과제 1이 끝나서 100점을 획득한다.

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution() {
    // 1. N분 입력 받기
    // 2. 스택 생성
    // 3. 문제 있을 시 원래 있던 시간에 -1분 처리하고 스택에 담기
    // 4. 문제 없을 시 스택 top -1분 처리하기
    // 5. 0분일 시 점수+, 스택에서 꺼내기
}

구현

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Stack;  
import java.util.StringTokenizer;  

public class Extra03IHateHomework {  
    public static void main(String[] args) throws IOException {  
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st;  
        int N = Integer.parseInt(bufferedReader.readLine());  
        Stack<Homework> stack = new Stack<>();  
        int answer = 0;  
        for (int i = 0; i < N; i++) {  
            st  = new StringTokenizer(bufferedReader.readLine());  
            int code = Integer.parseInt(st.nextToken());  
            if (code == 1) {  
                int score = Integer.parseInt(st.nextToken());  
                int duration = Integer.parseInt(st.nextToken());
                stack.push(new Homework(score, duration - 1));  
            } else {  
                if (!stack.isEmpty()) {  
                    Homework homework = stack.peek();  
                    homework.doHomework();  
                }  
            }  
            if (!stack.isEmpty() && 0 == stack.peek().getDuration()) {  
                answer += stack.pop().getScore();  
            }  
        }  
        System.out.println(answer);  
    }  

    public static class Homework {  
        private int score;  
        private int duration;  

        public Homework(int score, int duration) {  
            this.score = score;  
            this.duration = duration;  
        }  
        public int getScore() {  
            return this.score;  
        }  
        public int getDuration() {  
            return this.duration;  
        }  
        public void doHomework() {  
            this.duration--;  
        }    }  
}

• 굉장히 마음에 들지 않아!