[백준] 10773. 제로 (JAVA)

이번에 풀어 볼 문제는 <백준 10773번.  제로>이다.

https://www.acmicpc.net/problem/10773

📌 문제 탐색하기

목표

정확한 수들의 합 구하기

해야 할 것

1. 재현이가 부르는 수 저장하기

2. 0이 나오면 가장 최근에 쓴 수 지우기

3. 남아있는 정확한 수들의 합 구하기

입력

[첫줄] 주어질 수의 개수 K (1 ≤ K ≤ 100,000)

[둘째줄 ~ ] 각 줄에 정수가 1개씩 주어짐 ( 0 ~ 10^6 )

아이디어

1.재현이가 부르는 수를 어떤 자료 구조로 저장할까?

➡️ 0이 나올때마다 가장 최근에 쓴 수를 지우는 행위에서 Stack 자료구조가 적합할 것으로 판단

 

📌 코드 설계하기

1. ArrayDeque로 스택을 구현한다.

2. 숫자를 하나씩 스택에 쌓고, 0이 나오면 pop()을 실행한다.

3. 스택에 최종적으로 남은 숫자를 모두 더하여 출력한다.

 

📌 정답 코드

import java.io.*;
import java.util.ArrayDeque;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        int k = Integer.parseInt(br.readLine());

        for (int i=0; i<k; i++){
            int num = Integer.parseInt(br.readLine());
            if(num == 0){
                stack.pop();
            }else{
                stack.push(num);
            }
        }

        int result = 0;
        while(!stack.isEmpty()){
            result +=stack.pop();
        }

        System.out.println(result);
    }
}

 

📌 알게 된 것

[ int의 저장 범위 ] 

최소값 : - 2³¹

최대값 : 2³¹ - 1

=> 저장해야할 값의 범위가 2*10⁹ 을 넘어간다면 long 타입을 사용할 것