[Java] 백준 1541.잃어버린 괄호

➡️문제 링크

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

 

 

💡아이디어

처음 봤을 때는

이거 어떻게 풀라는 거지?

괄호의 위치를 하나하나 잡아가면서 풀어봐야 하나? 완전탐색인가?

이런 생각이 들며 나 실버2에서 무너지는 건가..? 싶었지만..!

펜을 잡고 노트에 문제에서 구하라는 것과 조건들을 쓰다보니 아래처럼 정리가 됐다.

(구) 이 식의 값을 최소로

• 모두가 + 면 다 더해버리면 됨
• 하나라도 - 가 있다면 앞에서부터 모두 더하면 X

처음에는 괄호를 직접 삽입해야 하나 싶었지만 다시 읽어보니 이 문제에서는 찐으로 괄호를 삽입하라는 걸 구하라는게 아니라

최솟값을 구하는 게 문제다!

그러므로 우리는 최솟값을 만들면 된다

그렇다면 어떻게 최솟값을 만들어야 할까?

문제에서 주어진 예제 대신 직접 케이스를 만들어 봤다

 

1 - 2 + 3 + 5 
이 경우에는 어떻게 만들어야 최솟값이 되는 걸까?

(1) 1 - 2 + 3 + 5 = 7
(2) 1 - (2 + 3) + 5 = 1
(3) 1 - (2 + 3 + 5 ) =  -9

...

이렇게 직접 만들어봤을 때
큰 값을 뺐을 때 값이 최소가 되는 것을 발견할 수 있다.

 

위의 과정을 통해, 나는

'-'가 나온다면 그 다음 -가 나올때까지 모두 더해서 : 2 + 3 + 5

전체적인 값에 해당 값을 빼버리기: 1 - (2 + 3 + 5)

라는 풀이를 생각했다

 

 

✏️문제 풀이

1. 구현 - 성공

위의 내 풀이 과정을 말 그대로 구현했다

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		List<Integer> nums = new ArrayList<>();
		List<Character> op = new ArrayList<>();
		op.add('0');
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < str.length(); i++) {
			if(str.charAt(i) == '+' || str.charAt(i) == '-') {		// 기호는 op 에 저장
				op.add(str.charAt(i));
				
				// 숫자로 바꾸기
				nums.add(Integer.parseInt(sb.toString()));
				sb = new StringBuilder();	// sb 초기화
			}else {
				sb.append(str.charAt(i));
			}
		}
		if(sb != null) nums.add(Integer.parseInt(sb.toString()));

		
		boolean [] visited = new boolean[op.size()];	// 해당 기호 사용 여부 판단
		//boolean [] nVisited = new boolean[nums.size()];
		
		// 구현
		int result = nums.get(0);	// 처음 숫자
		for(int i = 1; i < op.size(); i++) {
			if(op.get(i) == '-' && !visited[i]) {
				int idx = i+1;
				int tmp = nums.get(i);
				
				while(idx < op.size()) {							// 이 다음 -가 나올때까지 더해주기
					if(op.get(idx) == '-') break;	// - 나오면 탈출
					
					if(op.get(idx) == '+' && !visited[idx]) {
						tmp += nums.get(idx);
						visited[idx] = true;
					}
					idx++;
				}
				
				result -= tmp;
				
			}else if(op.get(i) == '+' && !visited[i]) {		// 덧셈 + 방문전 -> 그 다음 숫자 더해주기 
				result += nums.get(i);
				visited[i] = true;
			}
		}
		
		// 정답 출력
		System.out.println(result);



	}

}

 

 

 

2.  문자열 파싱 - 성공

문제를 풀고 뿌듯함으로 다른 사람들은 어떻게 풀었나~ 하고 풀이를 보는데

아니 다들 왜 이렇게 짧아요?

코드를 읽어보니 이렇게 쉽게 풀 수 있는 걸 빙빙 돌려서 푼 나도 대단하다^^ 라는 생각이 절로 들었다

 

기본 아이디어는 나랑 같다

'-' 기준으로 값들을 더해서 최종적으로는 그 값들을 빼기

대신, 나는 이걸 하나하나 숫자로 만들고, 여부를 판단했지만

문자열 파싱을 통해서 단 몇 줄로 끝을 낸 거였다.

 

1-2+3+5

(1) - 기준으로 문자열 파싱하기
 String [] str = {"1",  "2+3+5"};

(2) 해당 문자열의 각 원소에서 한 번더 "+"을 기준으로 파싱하기
"1"  -> {1}
"2+3+5" -> {"2", "3", "5"}

(3) 2를 수행할 때마다 각 숫자들을 더하기
{1}  -> 1
{"2", "3", "5"} - >10

(4) 3의 결과에서,  기존 str 배열에서 첫 번째 원소라면 그냥 더하고, 그 외라면 계속 빼기!
result  = 0;
1 -> result += 1 -> result = 1;
10 -> result -= rseult -> result = -9

 

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String [] str = br.readLine().split("-");		// - 기준으로 나누기
		
		int result = 0;
		for(int i = 0; i < str.length; i++) {
			int sum = 0;
			String [] tmp = str[i].split("\\+");	// 그 안에서 + 기준으로 나누기
			
			for(int j = 0; j < tmp.length; j++) {
				sum += Integer.parseInt(tmp[j]);
			}
			
			if(i == 0) result += sum;		// 처음 숫자만 더하기
			else result -= sum;				// 그 뒤로는 빼기
		}
		
		// 정답 출력
		System.out.println(result);

	}

}