글 읽기 - 틀렸습니다가 계속 나옵니다. 반례를 찾아주시면 감사하겠습니다.

quant1216 7년 전 0

제가 생각하는 모든 경우를 해봤는데 결과가 '틀렸습니다'가 계속 나옵니다.

예를 들면

(3+3)*(1+2)
(333+443)*(1+2)
((111+1)*(2-3))
(3*4)/3+7*4
14*15/7*21/15
(2+3+10)*7/5
285/(1+2+3+4+5)
(((153)))

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999/9

에서 모두 옳은 결과가 나왔습니다.

혹시나 반례를 찾거나 오류를 찾아주시면 감사하겠습니다.

package baekjoon_judge;

import java.math.BigInteger;
import java.util.*;
import java.lang.*;

//알고리즘 요약 : 괄호를 먼저 뽑아내어 이 값을 계산하고 계산 값을 queue에 저장.
//괄호를 포함한 substring을 a라는 문자로 바꾸어 놓고 이 후에 evaluation할 때, a가 나오면 queue에서 빼서 사용.
//괄호를 다 없애고 난 후, BigInteger library를 이용하여 연산자 우선순위에 따라 연산 수행.
//ROCK의 경우, 괄호의 갯수가 다르거나 연산자의 수와 피연산자의 수의 차이가 1이 아닐 경우, 출력.

public class Main {
	
	private static BigInteger eval(Vector<BigInteger> _operand,	Vector<Character> _operator){
		for(int i = 0; i < _operator.size(); i++){
			if(_operator.elementAt(i) == '*'){
				_operand.set(i, _operand.elementAt(i).multiply(_operand.elementAt(i + 1)));
				_operand.remove(i + 1);
				_operator.remove(i);
				i = -1;
			}
			else if(_operator.elementAt(i) == '/'){
				_operand.set(i, _operand.elementAt(i).divide(_operand.elementAt(i + 1)));
				_operand.remove(i + 1);
				_operator.remove(i);
				i = -1;
			}
		}
		
		for(int i = 0; i < _operator.size(); i++){
			if(_operator.elementAt(i) == '+'){
				_operand.set(i, _operand.elementAt(i).add(_operand.elementAt(i + 1)));
				_operand.remove(i + 1);
				_operator.remove(i);
				i = -1;
			}
			else if(_operator.elementAt(i) == '-'){
				_operand.set(i, _operand.elementAt(i).subtract(_operand.elementAt(i + 1)));
				_operand.remove(i + 1);
				_operator.remove(i);
				i = -1;
			}
		}
		return _operand.elementAt(0);
	}
	
	private static BigInteger find_parentheses(String _read_line){
		int 				check_parentheses	= _read_line.indexOf("(");
		String 				temp_string;
		Vector<BigInteger>	operand 			= new Vector<BigInteger>();
		Vector<Character>	operator 			= new Vector<Character>();
		Queue<BigInteger> 	a_store 			= new LinkedList<BigInteger>(); 
		String 				make_big = "";
		
		while(check_parentheses != -1){
			int parentheses = 1;
			for(int i = check_parentheses + 1; i < _read_line.length(); i++){
				if(_read_line.charAt(i) == '('){
					parentheses++;
				}
				else if(_read_line.charAt(i) == ')'){
					parentheses--;
					if(parentheses == 0) {
						temp_string = _read_line.substring(check_parentheses + 1, i);
						a_store.offer(find_parentheses(temp_string));
						//내부에 괄호가 또 있을 지 모르므로 checking하고 그 값을 저장.
						_read_line = _read_line.substring(0, check_parentheses) + 'a' + _read_line.substring(i + 1);
                        //괄호를 제거하고 제거한 곳에 a를 삽입.
						break;
					}
				}
			}
			check_parentheses = _read_line.indexOf("(");
		} // 괄호 checking 끝
		
		
		for(int i = 0; i < _read_line.length(); i++){
			if(_read_line.charAt(i) >= '0' && _read_line.charAt(i) <= '9'){
				make_big += _read_line.charAt(i);
			}
			else if(_read_line.charAt(i) == 'a'){
				operand.addElement(a_store.peek());
				a_store.poll();
			}
			else {
				operator.addElement(_read_line.charAt(i));
				if(make_big != ""){
					operand.addElement(new BigInteger(make_big));
					make_big = "";
				}
			}
		}
		
		if(make_big != ""){
			operand.addElement(new BigInteger(make_big));
		}

		return eval(operand, operator);
	}
		
	private static boolean checking_ROCK(String str){
		int 	bracket = 0, num_operator = 0;
		boolean start_operand = true;
		
		for(int i = 0; i < str.length(); i++){
			if(str.charAt(i) == '(') 		bracket++;
			else if (str.charAt(i) == ')') 	bracket--;
			else if (str.charAt(i) == '+' || str.charAt(i) == '-' || str.charAt(i) == '*' || str.charAt(i) == '/') {
				num_operator--;
				start_operand = true;
			}
			else{
				if(start_operand){
					num_operator++;
					start_operand = false;
				}
			}
		}
		
		if(bracket != 0 || num_operator != 1){
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String read_line = scan.nextLine(); 

		if(checking_ROCK(read_line)){
			System.out.println("ROCK");
			return;
		}
		System.out.println(find_parentheses(read_line));
		return;
	}
}

bupjae 7년 전 0

입력: )3(

원하는 출력: ROCK

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다가 계속 나옵니다. 반례를 찾아주시면 감사하겠습니다.

quant1216 7년 전 0

bupjae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말