[백준알고리즘-JAVA]10773번 풀이(제로) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 10773번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 10773 (제로)

문제

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

 

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

 

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

 

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

입력

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

 

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

 

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

출력

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

입력 출력 예제

성공코드

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

public class Main {

	static int T;
	static int sum = 0;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		Stack<Integer> stk = new Stack<>();
		
		for(int i = 0 ; i < T ; i++) {
			int temp = Integer.parseInt(br.readLine());
			
			if(temp == 0) {
				if(!stk.isEmpty()) {
				sum -= stk.pop();
				}
			}else {
				stk.push(temp);
				sum += temp;
			}
		}
		System.out.println(sum);
		}
}

 제로 알고리즘은 크게 어려울 것도 없습니다. 그냥 문제에서 하란대로 하나씩 해결하면 끝 STEP을 바로 따라가 보죠

---

알고리즘 흐름도

 입력 받기 -> 0 입력값 처리하기 -> 나머지 입력값 처리 하기 -> 출력하기

---

STEP1 입력값이 0일 때 처리하기

			if(temp == 0) {
				if(!stk.isEmpty()) {
				sum -= stk.pop();
				}

아주 간단합니다. 입력값으로 0이 들어오면 스택에서 가장 위의 값을 가져와서 뺴줍니다. 이때 스택이 비어있다면, 그냥 아무런 작동도 하지 않게 IF문을 하나 만들어주는 거만 고려하시면 됩니다.

---

STEP2 나머지 수가 들어왔을 경우 처리하기

			if(temp == 0) {
				if(!stk.isEmpty()) {
				sum -= stk.pop();
				}
			}else {
				stk.push(temp);
				sum += temp;
			}

만약 나머지 수가 들어왔을 경우 그 값을 넣어줍니다.

 

그런데 지금와서 다시 생각해보니 굳이 스택을 사용하지 않아도 쉽게 풀이했을 수 있을 것 같네요...

---

마지막으로 SUM을 출력해주면 제로 알고리즘은 너무 쉽게 해결이 되네요