[백준] no10773: 제로

문제

: 0과 0으로 제외된 숫자를 제외하고 모두 합

 

1) K = 입력될 숫자 개수

2) 두 번째 숫자부터는 합산할 숫자를 쌓음

3) 0이면 직전에 쌓인 숫자 제거

4) 남은 숫자 모두 더해서 출력

 

문제 링크 : https://www.acmicpc.net/problem/10773

---

원리

: K만큼 반복하며, 숫자가 나올때마다 스택에 담고, 0이 나올때마다 최근에 넣은 숫자 pop()

: 스택으로 모아서 최종적으로 합산

---

풀이방법

1) Stack사용

: 나오는 문자열이 0이면 stack.pop(), 0이 아니면 숫자로 형변환하여 stack.push()

: 남은 숫자를 stack이 빌 때 까지 pop()해서 sum

2) Deque사용 (*추천 | 속도, 메모리향상)

: 나오는 문자열이 0이면 deque.pollLast(), 0이 아니면 숫자로 형변환하여 deque.push() 또는 addLast()

: 남은 숫자를 deque가 빌 때 까지 poll()해서 sum

* 주의사항: deque에서 pop()은 앞에서 부터 pop()이 되므로 pollLast() 혹은 pollFirst()로 구분해서 사용하기 권장

* 0을 비교할 때 문자열로 비교 후 0이 아니면 형변환하는것이 0을 형변환하지 않아 속도 및 메모리에 유리함

---

나의 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());
        Deque<Integer> dq = new ArrayDeque<>();

        for(int i=0; i<K ; i++) {
            String num = br.readLine();
            if(num.equals("0")) dq.pollLast();
            else dq.add(Integer.parseInt(num));
        }

        int sum = 0;
        while(!dq.isEmpty()) sum += dq.pollFirst();
        System.out.println(sum);
    }
}