[JAVA] 백준10773: 제로

 

숫자를 넣다가, 0이 나오면 가장 최근의 수를 지우고, 또 넣다가 또 0이 나오면 가장 최근의 수를 지운 다음,

남아있는 숫자들의 합을 구하는 문제이다.

 

지금 이 알고리즘은 자료구조에 관련한 문제인지라,

Stack 냄새가 폴폴 났다.

Stack은 후입선출(LIFO) 방식의 자료구조니까, 문제 풀이에 적합하다.

 

배열로 풀기

문제라면 내가 Stack을 사용해본적이 없기 때문에, 처음에는 그냥 배열을 만들어서 풀으려고 했었다.

배열로 풀어도 된다.

가장 최근의 숫자에 해당하는 인덱스를 변수로 만들어준다.

이때 이 변수는 -1로 초기화하고, 입력이 0이 나올때, 그리고 변수가 -1 이상일 때 감소시켜준다.

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int last = -1; // 마지막 숫자의 인덱스를 표시한 변수
        int k = sc.nextInt();
        int[] arr = new int[k];

        for (int i = 0; i < k; i++) {
            int number = sc.nextInt();
            if (number == 0) {
                //last가 -1보다 큰 경우에만 감소시킴
                if (last > -1) {
                    last--;
                }
            } else {
                last++;
                arr[last] = number;
            }
        }
		sc.close();
        
        int sum = 0;
        for (int i = 0; i <= last; i++) {
            sum += arr[i];
        }
        System.out.println(sum);
    }
}

 

암튼 대충 이렇다.

 

 

그리고 Stack으로 풀어 보기.

Stack으로 풀기

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt(); // 첫 줄에서 숫자의 개수 K를 읽음
        Stack<Integer> stack = new Stack<>(); // Stack 초기화

        for (int i = 0; i < K; i++) {
            int num = sc.nextInt(); // 숫자를 한 개씩 읽어옴
            
            if (num == 0) {
                // num이 0인 경우: 스택에서 마지막으로 추가한 숫자를 제거
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                // num이 0이 아닌 경우: 스택에 숫자를 추가
                stack.push(num);
            }
        }
        sc.close();

        // 스택에 남아있는 모든 숫자 더하기
        int sum = 0;
        for (int number : stack) {
            sum += number;
        }

        System.out.println(sum);
    }
}