스파르타 알고리즘 트랙 문제 3일차 - 3 #10773 제로

문제

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

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

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

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

 

해결 과정

0인 입력이 들어올 때마다 가장 최근 값을 없애는 LIFO 형식의 자료 구조가 필요하다. 따라서 터렛 문제에서 사용했던 Stack을 사용해야 한다는 것을 알 수 있다.

 

Stack을 사용해야 한다는 것을 알았다면 구현은 간단하다. 입력으로 0을 받았다면 기존에 숫자를 저장해 두었던 Stack에서 값을 하나 지우면 된다. 다만 Stack이 비어 있을 때 값을 빼려고 하면 에러가 발생하므로 Stack이 비어 있을 때는 넘어가는 것이 필요하다.

import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class Main {     public static void main(String[] args) throws IOException {         BufferedReader a = new BufferedReader(new InputStreamReader(System.in));         int total = 0;         int N = parseInt(a.readLine());         Stack<Integer> arr = new Stack<>();         while (N!=0){             int order = parseInt(a.readLine());             if (order == 0) {                 if (!arr.empty()) {                     total -= arr.pop();                 }             }             else {                 arr.push(order);                 total += order;             }             N--;         }         System.out.println(total);     } }

Stack에 저장이 끝난 후 값을 하나씩 pop 메소드로 불러오면서 계산해도 무방하다. 단지 어차피 더할 값 저장할 때 미리 더하고 삭제할 때 미리 빼면 결과를 조금 더 빨리 확인할 수 있지 않을까 라는 생각에 total을 구현하였고, 동일하게 돌아가는 것을 확인해 위처럼 코드를 작성하였다.

 

total로 한번에 계산하면 Stack은 필요없지 않나 라는 생각에 Stack 없이 구현해 보려 했는데, 0이 입력되었을 때 뺄 값을 저장할 공간이 필요했기에 결국 Stack을 사용하게 되었다.