10773번 - 제로

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

public class Main {
	
	static String add(String num, String addend) {
		StringBuilder sb = new StringBuilder();
		int num_size = num.length();
		int addend_size = addend.length();
		int min = Math.min(num_size, addend_size);
		int max = Math.max(num_size, addend_size);
		boolean carry = false;
		int a, b, sum;
		for(int i=0;i<min;i++) {
			a = Integer.parseInt(num.substring(num_size-1-i, num_size-i));
			b = Integer.parseInt(addend.substring(addend_size-1-i, addend_size-i));
			sum = a + b;
			if(carry == true) {
				sum += 1;
			}
			if(sum >= 10) {
				carry = true;
				sum -= 10;
			} else {
				carry = false;
			}
			sb.insert(0, sum);
		}
		for(int i=min;i<max;i++) {
			if(num_size >= addend_size) {
				a = Integer.parseInt(num.substring(num_size-1-i, num_size-i));
				sum = a;
				if(carry == true) {
					sum += 1;
				}
				if(sum >= 10) {
					carry = true;
					sum -= 10;
				} else {
					carry = false;
				}
				sb.insert(0, sum);
			}
			else {
				a = Integer.parseInt(addend.substring(addend_size-1-i, addend_size-i));
				sum = a;
				if(carry == true) {
					sum += 1;
				}
				if(sum >= 10) {
					carry = true;
					sum -= 10;
				} else {
					carry = false;
				}
				sb.insert(0, sum);
			}
		}
		if(carry) {
			sb.insert(0, 1);
		}
		return sb.toString();
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		Stack<String> stack = new Stack<>();
		String item;
		String answer = "0";
		for(int i=0;i<K;i++) {
			item = br.readLine();
			if(item.equals("0")) {
				stack.pop();
			}
			else {
				stack.push(item);
			}
		}
		while(!stack.isEmpty()) {
			answer = add(answer, stack.pop());
		}
		System.out.println(answer);
		br.close();
	}
}

0이 나오면 바로 앞의 수를 지우는 것 자체는 스택을 이용하면 매우 간단하게 해결할 수 있습니다. 하지만 결과가 1000000 * 100000까지의 수가 될 수 있기 때문에 int 외의 다른 방법을 사용해서 계산해야 합니다.

이 경우 Java에서는 BigInteger를 사용해도 되지만 문자열을 이용해서 계산하는 방법으로 해결했습니다.

 

문자열을 이용할 경우 수기식으로 계산을 할 때 이용하는 세로셈법을 그대로 알고리즘으로 옮겨서 문자열로 덧셈을 구현할 수 있습니다. 위의 코드에서는 더하는 두 수에서 짧은 길이까지 같은 자리끼리 더하고 남은 수를 계속 0인덱스 자리(가장 왼쪽)에 붙여서 이어갑니다. 이 때 10이 넘을 경우 다음 자리에 1을 넘겨주는 carry를 항상 고려합니다.