📌 문제

[10773] 제로

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

⬇️ 입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 0 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

⬆️ 출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 2^31-1보다 작거나 같은 정수이다.

💡 코드

✅ 가장 최근에 쓴 수를 지우는 것은 곧 후입선출인 스택과 같으므로 Stack 클래스를 사용하여 문제를 해결했다. 입력값이 0인 경우에는 pop() 메서드를 사용하여 맨 위의 요소를 삭제하고, 이외의 경우에는 push(n) 메서드를 통해 입력받은 n을 stack에 저장한다.

입력이 끝나면 for문을 사용하여 최종적으로 stack에 남아있는 수들의 합을 구한다. pop() 메서드를 사용하여 맨 위의 요소들을 꺼내면서 반환된 값은 sum에 누적합시킨다. 처음에는 size() 메서드를 for문의 조건문에 사용했었는데, 그렇게 되면 pop()을 통해 꼭대기 요소를 날릴 때마다 개수가 줄어들어 반복횟수가 달라져 모든 수를 더하지 못하게 된다. 그래서 변수 size에 개수를 따로 저장하여 반복문을 돌려줬다.

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Stack<Integer> stack = new Stack<>();
		int k = Integer.parseInt(br.readLine());
		for(int i=0;i<k;i++) {
			int n = Integer.parseInt(br.readLine());
			
			if(n == 0) stack.pop();
			else stack.push(n);
		}
		
		int sum = 0; int size = stack.size();
		for(int i=0;i<size;i++) {
			sum += stack.pop();
		}
		bw.write(sum + "");
		
		br.close();
		bw.close();
	}
}

➕ 다른 사람의 코드 : size 변수와 pop() 메서드를 따로 사용할 필요없이 확장 for문을 사용하면 간단하게 해결할 수 있었다! 대부분 일반 for문을 사용하여 문제를 해결했는데, 이제부터 자료구조 요소들을 출력해야 한다면 확장 for문을 사용하는 습관을 들여야겠다..

int sum = 0;
for(int num : stack) {
	sum += num;
}

✅ 이번 단계가 스택/큐 단계라 Stack 클래스를 사용하여 해결하였는데, 배열로 해결한 코드도 발견해서 나도 클래스를 사용하지 않고 배열로 스택을 직접 구현하여 풀어봤다!

최대 k개의 값이 저장될 수 있도록 크기가 k인 배열 arr[]을 생성하고, for문을 통해 입력받은 값을 배열에 저장해준다. 이 때, 입력값 num이 0인 경우에 마지막 인덱스의 값을 삭제해야하므로 값을 저장할 때마다 idx에 마지막으로 값이 저장된 인덱스의 값을 저장해주어야 한다.

값이 삭제되기 위해서는 무조건 값이 있어야 하므로 idx의 초기값을 0으로 설정하고, num이 0이 아닌 경우에 idx번 인덱스에 num을 저장한 후 idx 값을 1 증가시킨다. 다음 반복에서 또 num이 0이 아니면 idx+1번 인덱스에 num을 저장하고, num이 0이면 idx-1번의 값을 삭제해야 하는데, 배열에는 삭제 개념이 없으므로, 값을 0으로 초기화 해준다. 마지막 인덱스 값을 삭제하면 인덱스는 idx-1 상태가 되고, 다음 반복에서 num이 0이 아니면 값을 삭제했던 idx-1번 인덱스에 값을 다시 저장한 후 계속 반복을 수행한다.

반복을 마치면 idx에 마지막으로 값이 저장된 인덱스가 저장되어 있으므로, 해당 요소까지 반복을 수행하여 값이 0이 아닌 요소들을 sum에 누적합 시키면 된다.

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int k = Integer.parseInt(br.readLine());
		int[] arr = new int[k];
		
		int idx = 0;
		for(int i=0;i<k;i++) {
			int num = Integer.parseInt(br.readLine());
			
			if(num == 0) arr[--idx] = 0;
			else arr[idx++] = num;
		}

		int sum = 0;
		for(int i=0;i<idx;i++) {
			sum += arr[i];
		}
		bw.write(sum + "");
		
		br.close();
		bw.close();
	}
}