백준_제로_10773, 백준_과제는 끝나지 않아!_17952

제로

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력

4
3
0
4
0

예제 출력

0

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const K = +input[0]; // 정수 K

const numbers = []; // 장부
for (let i = 1; i <= K; i += 1) {
  const number = +input[i];
  if (number !== 0)
    numbers.push(number); // 0이 아닌 경우 장부에 숫자 넣기
  else numbers.pop(); // 0인 경우 가장 마지막에 들어간 숫자 빼내기
}

const totalSum = numbers.reduce((sum, number) => sum + number, 0); // 최종 장부 총합 구하기

console.log(totalSum);

풀이 및 해설

• 스택 이용
  • 0이 아닌 경우 숫자 하나씩 배열에 넣기
  • 0이 나오면 가장 위에 있는 숫자 빼기
• 최종적으로 남아있는 숫자 더하기

---

과제는 끝나지 않아!

문제

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

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

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

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

입력

첫째 줄에 이번 학기가 몇 분인지를 나타내는 정수 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

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 이번 학기의 시간(분)

const tasks = []; // 미뤄둔 과제 정보 배열
let currentTasks = [0, 0]; // 현재 수행하고 있는 과제 정보
let answer = 0; // 얻을 수 있는 총점
for (let i = 1; i <= N; i += 1) {
  const [num, score, time] = input[i].split(' ').map(Number);
  if (num === 1) {
    if (currentTasks[0] === 0)
      currentTasks = [score, time - 1]; // 처음 과제 시작하는 경우
    else {
      tasks.push([currentTasks[0], currentTasks[1]]); // 새로운 과제 나온 경우 하고 있던 과제 잠시 미루기
      currentTasks = [score, time - 1]; // 새로운 과제 수행
    }
  } else if (num === 0) currentTasks[1] -= 1; // 과제가 주어지지 않은 경우 기존의 과제 계속 수행

  // 현재 수행하고 있는 과제가 끝난 경우
  if (currentTasks[1] === 0) {
    answer += currentTasks[0]; // 해당 과제 점수를 총점에 더해주기
    if (tasks.length > 0) currentTasks = tasks.pop(); // 미뤄둔 과제가 있는 경우 최근에 넣어둔 과제 먼저 수행
  }
}

console.log(answer);

풀이 및 해설

• 스택 이용
  1. 현재 시점에 과제가 주어진 경우, 기존에 하고 있던 과제가 있는 경우 tasks 배열에 넣기
  2. 현재 시점에 과제가 없는 경우, 기존에 하고 있던 과제 하기
     1. 만약, 기존에 하고 있던 과제가 끝난 경우 tasks 배열에서 가장 최근에 들어간 과제 꺼내서 다시 하기
  3. 과제를 완성할 때마다 해당 과제의 점수 더하기