백준 1541 잃어버린 괄호

노문택·2022년 5월 29일
0
post-custom-banner

https://www.acmicpc.net/problem/1541

잃어버린 괄호

수식은 + - 으로 이루어지고 수를 괄호로 묶어서 최솟값을 만들기

정말 간단한문제

얘를들어

30 -25 + 25이면
30 - (25+25) = -20
으로만들으라는뜻

그래서 -로나오면 ( 로만들고 그다음에 스택에 넣어서 꺼내면서 계산을 하려고했는데
그럴필요가없엇다

그냥 - 가 나오면 그다음부터 나오는숫자들은 다 빼주면 끝

WHY ? =>

그리디 알고리즘을 푸는 핵심인거같다

그리디 적인생각을 로직을 짠다 => EdgeCase에 대해 고민을하고 적용한다

수식이 나오는 경우는 다음과 같은경우인거같다

    • // - + // + + // + -

    이렇게 4가지 케이스

    하지만 괄호로 묶어서 적게표현할수있다면 어떻게될까?

    • // -( + ) // + + // + - 결국 이렇게 된다 그러므로 그냥 - 된이후로는 다빼주면됨 그래서 코드는 다음과같다.
      import java.io.*;
      import java.util.*;

public class 잃어버린괄호 {

public static void main(String[] args) throws Exception {
	// TODO Auto-generated method stub
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String line = br.readLine();
	
	int sum=0;

	String number="";
	int curnum = 0;
	boolean minuseflag = false;
	boolean firstflag = false;
	for(int i=0;i<line.length();i++) {
		char cur = line.charAt(i);
		if(cur-'0'>=0 && cur-'0'<10) {
			number = ""+ number+cur;
		}
		else {
			if(!firstflag) { //첫번째가 들어왔을때 
				sum += Integer.parseInt(number);
				firstflag= true;
				
				if(cur=='-') {
					minuseflag= true;
				}
				number="";
				continue;
			}
			
			if(!minuseflag) {
				sum += Integer.parseInt(number);
				if(cur=='-') {
					minuseflag = true;
				}
			}
			else {
				sum -= Integer.parseInt(number);
			}
			number="";
		}
	}
	
	if(!minuseflag) {
		sum += Integer.parseInt(number);
	}
	else {
		sum -= Integer.parseInt(number);
	}
	
	
	System.out.println(sum);
}

}


![](https://velog.velcdn.com/images/tekies09/post/11bc1143-d46e-4008-99e4-5a8ebb003ce9/image.png)


얼른 실버 1로 ㄱㄱ 





profile
노력하는 뚠뚠이
post-custom-banner

0개의 댓글