πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.10773 제둜 문제 풀이 - java

πŸ“– 문제

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

λ‚˜μ½”λ” κΈ°μž₯ μž¬λ―Όμ΄λŠ” 동아리 νšŒμ‹μ„ μ€€λΉ„ν•˜κΈ° μœ„ν•΄μ„œ μž₯λΆ€λ₯Ό κ΄€λ¦¬ν•˜λŠ” 쀑이닀.

μž¬ν˜„μ΄λŠ” 재민이λ₯Ό λ„μ™€μ„œ λˆμ„ κ΄€λ¦¬ν•˜λŠ” 쀑인데, μ• μ„ν•˜κ²Œλ„ 항상 μ •μ‹ μ—†λŠ” μž¬ν˜„μ΄λŠ” λˆμ„ μ‹€μˆ˜λ‘œ 잘λͺ» λΆ€λ₯΄λŠ” 사고λ₯Ό 치기 μΌμ‘€μ˜€λ‹€.

μž¬ν˜„μ΄λŠ” 잘λͺ»λœ 수λ₯Ό λΆ€λ₯Ό λ•Œλ§ˆλ‹€ 0을 μ™Έμ³μ„œ, κ°€μž₯ μ΅œκ·Όμ— μž¬λ―Όμ΄κ°€ μ“΄ 수λ₯Ό μ§€μš°κ²Œ μ‹œν‚¨λ‹€.

μž¬λ―Όμ΄λŠ” μ΄λ ‡κ²Œ λͺ¨λ“  수λ₯Ό λ°›μ•„ 적은 ν›„ κ·Έ 수의 합을 μ•Œκ³  μ‹Άμ–΄ ν•œλ‹€. 재민이λ₯Ό λ„μ™€μ£Όμž!

μž…λ ₯

첫 번째 쀄에 μ •μˆ˜ Kκ°€ 주어진닀. (1 ≀ K ≀ 100,000)

이후 K개의 쀄에 μ •μˆ˜κ°€ 1κ°œμ”© 주어진닀. μ •μˆ˜λŠ” 0μ—μ„œ 1,000,000 μ‚¬μ΄μ˜ 값을 가지며, μ •μˆ˜κ°€ β€œ0” 일 κ²½μš°μ—λŠ” κ°€μž₯ μ΅œκ·Όμ—

μ“΄ 수λ₯Ό μ§€μš°κ³ , 아닐 경우 ν•΄λ‹Ή 수λ₯Ό μ“΄λ‹€.

μ •μˆ˜κ°€ β€œ0”일 κ²½μš°μ— μ§€μšΈ 수 μžˆλŠ” μˆ˜κ°€ μžˆμŒμ„ 보μž₯ν•  수 μžˆλ‹€.

좜λ ₯

μž¬λ―Όμ΄κ°€ μ΅œμ’…μ μœΌλ‘œ 적어 λ‚Έ 수의 합을 좜λ ₯ν•œλ‹€.

πŸ” 접근법

boj Q.10773 제둜 λ¬Έμ œμž…λ‹ˆλ‹€.

μž…λ ₯으둜 kκ°€ 주어지고

이후 k개의 쀄에 μ •μˆ˜κ°€ 1κ°œμ”© μ£Όμ–΄μ§‘λ‹ˆλ‹€.

μ—¬κΈ°μ„œ μ •μˆ˜κ°€ β€œ0”일 κ²½μš°μ—λŠ”

κ°€μž₯ μ΅œκ·Όμ— μ“΄ 수λ₯Ό μ§€μš°κ²Œ λ©λ‹ˆλ‹€

κ°€μž₯ μ΅œκ·Όμ— μ“΄ μˆ˜κ°€ λ¨Όμ € μ§€μ›Œμ§ => κ°€μž₯ λ‚˜μ€‘μ— μž…λ ₯된 μˆ˜κ°€ λ¨Όμ € μ§€μ›Œμ§

LIFO (LAST IN FIRST OUT)

λ°”λ‘œ μŠ€νƒμ„ μ΄μš©ν•΄μ„œ 풀이할 수 μžˆμŠ΅λ‹ˆλ‹€.

숫자λ₯Ό μŠ€νƒμ— μ°¨κ·Όμ°¨κ·Ό μŒ“μ•„μ£ΌλŠ”λ° λŒ€μ‹  μ •μˆ˜ 0을 λ§Œλ‚˜λ©΄

0을 λ„£μ§€μ•Šκ³  졜근의 숫자λ₯Ό μŠ€νƒμ—μ„œ κΊΌλ‚΄μ€λ‹ˆλ‹€. pop

λͺ¨λ“  숫자λ₯Ό μ²˜λ¦¬ν•˜κ³  λ‚˜μ„œ

μŠ€νƒμ— λ‚¨μ•„μžˆλŠ” 수λ₯Ό ν•˜λ‚˜μ”© μ°¨κ·Όμ°¨κ·Ό λΉΌμ„œ

합을 ꡬ해주면 닡을 λ„μΆœ ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

πŸ’» μ½”λ“œ

package problem.stack;

import java.io.*;
import java.util.Stack;

public class Main_10773 {
    static int k;
    static Stack<Integer> stack;
    static int sum = 0;
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        stack = new Stack<>();
        solve();
        bw.flush();
        bw.close();
    }

    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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);
            }
        }
        while (!stack.isEmpty()){
            sum+=stack.pop();
        }
        System.out.println(sum);
        br.close();
    }
}

Written on February 19, 2021