[BOJ] 10773번 : 제로

📌 풀이

---

📍 문제 이해 & 구현에 필요한 자료구조

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
➡️ 재현이가 가장 최근에 재민이가 쓴 수를 지우는 과정은 후입선출(LIFO, Last-In-First-Out) 원칙을 따르고 있으므로, 스택 자료구조를 사용해 문제를 해결한다.

📍 구현 단계

1. K개의 숫자를 입력받아 stack 자료구조에 저장한다.
   1-1. 만약 0을 입력받으면, stack의 top에 있는 숫자를 삭제시킨다.
2. stack에 담긴 모든 원소의 합을 구한다.

📌 문제 해결

---

📍 기댓값과 다른 결괏값

package ch05_Stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class p10773 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int K = Integer.valueOf(br.readLine());
		
		Stack<Integer> stack = new Stack<>();
		
		for (int i = 0; i < K; i++) {
			int input = Integer.valueOf(br.readLine());
			
			if (input == 0) {
				stack.pop();
				continue;
			}
			
			stack.add(input);
		}
		
		int sum = 0;
		for (int i = 0; i < stack.size(); i++) {
			sum += stack.pop();
		}
		
		System.out.println(sum);
	
	}

}

문제 원인

아래 코드대로 구현할 시 스택의 크기가 반복될 때마다 변경되고, 예상치 못한 결과가 발생할 수 있다.

int sum = 0;
for (int i = 0; i < stack.size(); i++) {
			sum += stack.pop();
}

수정한 코드

int sum = 0;
while(!stack.isEmpty()) {
			sum += stack.pop();
}

stack.size() 대신에 stack.isEmpty() 메서드를 사용하여 스택이 비어 있는지 확인해 반복문을 돈다.

📌 최종 코드

---

package ch05_Stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class p10773 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int K = Integer.valueOf(br.readLine());
		
		Stack<Integer> stack = new Stack<>();
		
		for (int i = 0; i < K; i++) {
			int input = Integer.valueOf(br.readLine());
			
			if (input == 0) {
				stack.pop();
				continue;
			}
			
			stack.add(input);
		}
		
		int sum = 0;
		while(!stack.isEmpty()) {
			sum += stack.pop();
		}
		
		System.out.println(sum);
	
	}
}

📌 참고

---

📍 자바의 int 데이터 타입은 32비트를 사용하며, 부호 비트를 포함하여 31비트의 값을 저장한다. 따라서 int형은 2의 31승의 범위를 표현할 수 있다.

📍 스택 STL 함수

• stack.add(x)
• stack.pop()
• stack.size() : 스택에 포함된 요소의 개수를 반환