문제
정수를 하나씩 입력받는데, 0이 들어오면 가장 최근에 입력한 수를 지운다. 모든 입력이 끝난 뒤 남아있는 수들의 합을 구하는 문제다.
입력
- 첫째 줄: 입력 횟수 K
- 이후 K개 줄: 정수 (0 또는 양의 정수)
출력
남아있는 수들의 합
예제
| 입력 | 출력 |
|---|---|
4 1 3 5 4 | 9 (1+3+5, 4는 0에 의해 제거됨) |
풀이
입력 순서를 유지하면서 마지막 원소를 제거해야 하므로 스택(LIFO)이 적합하다. 0이 아닌 수는 스택에 push하고, 0이면 pop해서 이전 수를 제거한다.
- K를 입력받고 크기 K의 배열로 스택을 직접 구현한다(
top = -1). - K번 반복하며 입력값이 0이 아니면
push, 0이면pop한다. - 반복 종료 후 스택에 남은 원소들을 모두 pop해 합산한다.
- 합계를 출력한다.
핵심 아이디어: "가장 최근 입력값 취소" 연산은 스택의 pop 연산과 정확히 대응된다. 문제에서 0의 개수가 나머지 수보다 적음을 보장하므로 언더플로우 예외처리가 불필요하다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day15BOJ10773제로 { // 10773
static int[] stack;
static int top = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
stack = new int[N];
for (int n = 0; n < N; n++) {
int i = Integer.parseInt(br.readLine());
if (i != 0) {
push(i);
} else {
pop();
}
}
int sum = 0;
int s = top + 1;
for (int n = 0; n < s; n++) {
sum += pop();
}
System.out.println(sum);
br.close();
}
// 문제에서 0의 갯수가 나머지 수 갯수보다 작음을 보장함.
private static int pop() {
return stack[top--];
}
private static void push(int i) {
stack[++top] = i;
}
}복잡도
- 시간: O(N)
- 공간: O(N)