[백준] 1541번 잃어버린 괄호 (그리디 알고리즘_JAVA)

 

이 문제 또한

싸피 다닐 때 풀지 못했던 문제다.

 

다시 도전하려고 했는데,

아이디어가 전혀 떠오르지 않아서

힌트를 봤다.

 

그리디 알고리즘이라고 보이자마자

아, 어떻게 풀어야겠다가 바로 떠올랐다!

 

 

---

문제

 

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

1541번: 잃어버린 괄호

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 그리디 알고리즘

그리디 알고리즘은 현재 할 수 있는 선택에서 가장 좋은 선택을 이어나가는 것이다.

좋은 선택의 연속이 최적의 결과를 만든다는 것의 알고리즘인데,

작은 수를 만들기 위해서 +, - 기호 중 - 기호 뒤에 있는 숫자를 모두 더하면 충분할 것이라 생각했다.

 

풀이 과정

1.

연산 식을 입력받는다.

그리고 분자배열로 변경 후 숫자와 연산기호를 구분하여 list형식으로 변경한다.

여기서 주의해야 할 점은 연산 기호가 맨 처음에 올 수 있으므로 num의 값이 ""이 아닐 때만 list에 넣어야 한다.

 

2.

반복문을 실행하면서 list를 처음부터 끝까지 값을 확인한다.

 

- 현재 list의 값이 연산 기호 + 라면 다음으로 넘어간다.

- 현재 list의 값이 연산 기호 - 라면, 뒤에 또다른 - 기호를 만나기 전까지의 숫자를 모두 더한다.

  그럼 모두 더한 값에 -를 곱한 후 total에 더한다.

  인덱스를 현재 인덱스로 변경한다. 현재 인덱스가 idx-1인 이유는 while 반복문에서 idx++를 해주기 때문이다. 

- 현재 list의 값이 숫자라면 total에 더한다.

 

3.

반복문이 종료되면 total값을 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_1541_잃어버린괄호 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String str = sc.next();
		char[] charr = str.toCharArray();
		
		List<String> list = new ArrayList();
		
		String num = "";
		for(int i=0; i<charr.length; i++) {
			if('0'<=charr[i] && charr[i]<='9') num+=charr[i];
			else {
				if(!num.equals("")) list.add(num);
				num = "";
				
				list.add(String.valueOf(charr[i]));
			}
		}
		
		list.add(num);
		
		int total = 0;
		for(int i=0; i<list.size(); i++) {
			//+를 만난 경우
			if(list.get(i).equals("+")) continue;
			
			//-를 만난 경우
			else if(list.get(i).equals("-")) {
				int sum = 0;
				int idx = i+1;
				
				while(idx<list.size() && !list.get(idx).equals("-")) {
					if(!list.get(idx).equals("+")) sum+=Integer.parseInt(list.get(idx));
					
					System.out.println("sum : " +sum);
					idx++;
				}
				
				total+=(sum*-1);
				i=idx-1;
			}
			
			//숫자인 경우
			else {
				total+=Integer.parseInt(list.get(i));
			}
			
		}
		
		//출력
		System.out.println(total);
	}
}

 

 

(❁´◡`❁)

끝!