백준 - 19591 독특한 계산기

www.acmicpc.net/problem/19591

19591번: 독특한 계산기

 

1. 유형

스트링 파싱, 구현, 덱

 

2. 자료구조

리스트, 덱

 

3. 풀이

• 기호, 문자열만 덱에 저장
• 우선순위대로 계산
• 예외처리(처음 음수값, 의미없는 0)

처음 주어지는 문자열을 파싱해서 기호, 숫자를 나누어 덱에 저장한다. 굳이 덱을 안쓰고 arrayList를 사용해도 될듯

파싱을 할때 주의할점은 첫 숫자가 음수인 경우이다. 이를 주의하자

또한, 0001처럼 무의미 0이 들어오는 경우에도 주의해야한다. 이는 flag를 사용해서 0을 걸러준다.

 

나머지는 우선순위에 따라 구현해주면 된다.

 

4. 디버깅

1. 문제를 풀면서 97퍼센트에서 계속 numberformat오류가 났다.

Long.valueof를 사용할때 문자가 들어오면 나오는 에러이다.

이 에러 수정하느라 몇시간을 날렸는데, -0값이 들어오면 나오는 에러이다.

 

이상한점은 -2^62 ~ 2^63 범위에서 -0이 들어오는가이다. 이는 문제의 오류인거 같다.

 

2. Long타입 신경써주자. Integer로 썼다가 한번 틀림

 

5. 코드

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

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static String str;
	static Deque<Long> num;
	static Deque<Character> cmd;
	static long ans;
	static void parse() throws IOException {
		ans=0;
		st = new StringTokenizer(in.readLine());
		str = st.nextToken();
		num = new LinkedList<>();
		cmd = new LinkedList<>();
		String str_int = "";

		int fir_idx = 0;
		if (str.charAt(0) == '-') {
			str_int += '-';
			fir_idx++;
		}
		boolean flag = false;
		for (int i = fir_idx; i < str.length(); i++) {
			char k = str.charAt(i);
			if (k == '*' || k == '/' || k == '+' || k == '-') {
				if(flag) {
					num.add(Long.valueOf(str_int));
				}else {
					num.add(Long.valueOf("0"));
				}
				str_int = "";
				cmd.add(k);
				flag = false;
			} else {
				if(k!='0') {//맨 앞에 0이 나오는 경우
					flag = true;
				}
				if(flag)
					str_int += k;
			}
		}
		if (!str_int.equals("-") && !str_int.equals("")) {
			num.add(Long.valueOf(str_int));
		}else
			num.add(Long.valueOf("0"));
	}

	static void check() {
		while (cmd.size() > 1) {
			char pre_cmd = cmd.getFirst();
			char last_cmd = cmd.getLast();
			long pre_num = num.removeFirst();
			long last_num = num.removeLast();
			long preSec_num = num.getFirst();
			long lastSec_num = num.getLast();
			if ((pre_cmd == '*' || pre_cmd == '/') && (last_cmd == '+' || last_cmd == '-')) {
				// 앞 선택
				select_first(last_num, calc(pre_num, preSec_num, pre_cmd));
			} else if ((pre_cmd == '+' || pre_cmd == '-') && (last_cmd == '*' || last_cmd == '/')) {
				// 뒤 선택
				select_last(pre_num, calc(lastSec_num, last_num, last_cmd));
			} else {
				// 크기 비교
				long pre_res = calc(pre_num, preSec_num, pre_cmd);
				long last_res = calc(lastSec_num, last_num, last_cmd);
				if(pre_res > last_res) {
					select_first(last_num, calc(pre_num, preSec_num, pre_cmd));
				}else if(pre_res < last_res) {
					select_last(pre_num, calc(lastSec_num, last_num, last_cmd));
				}else {
					//앞 선택
					select_first(last_num, calc(pre_num, preSec_num, pre_cmd));
				}
			}
		}
	
		if(cmd.size()==1) {
			ans = calc(num.removeFirst(), num.removeFirst(), cmd.removeFirst());
		}else {
			ans = num.removeFirst();
		}
	}
	static long calc(long a, long b, char c) {
		if(c=='*') {
			return a*b;
		}else if(c=='/') {
			return a/b;
		}else if(c=='+') {
			return a+b;
		}else  {
			return a-b;
		}
	}
	static void select_first(long last_num, long res) {
		num.addLast(last_num);//맨 뒤 숫자
		num.removeFirst();//맨 앞 숫자
		num.addFirst(res);
		cmd.removeFirst();//맨 앞 연산자				
	}
	static void select_last(long pre_num, long res) {
		num.addFirst(pre_num);//맨 앞 숫자
		num.removeLast();//맨 뒤 숫자
		num.addLast(res);
		cmd.removeLast();//맨 뒤 연산자
	}
	public static void main(String[] args) throws IOException {
		parse();// 파싱
		check();// 우선순위 탐색
		System.out.println(ans);
	}
}