[백준 1541] 잃어버린 괄호

[문제 바로가기]👇

1541번: 잃어버린 괄호

💡풀이💡

식이 주어졌을 때 최소의 값을 만들기

>> 가장 작은 수 - 가장 큰 수 를 만들면 되지 않을까??? 하는 생각으로 접근

식에 여러 숫자와 여러 연산자가 있겠지만 가장 간단한 형태로 생각해보면 마이너스 연산자(-)를 기준으로 가장 작은 수와 가장 큰 수가 나뉘게 된다.

• 마이너스 연산자 + 1만큼의 수의 덩어리가 생기게 됨

 

마이너스가 나오기 전까지 앞의 숫자들을 모두 계산해서 하나의 수 덩어리를 만들고 마이너스가 나온 이후의 숫자들을 모두 더해 또 다른 하나의 수 덩어리를 만듦

• 마이너스 앞에 만들어지는 덩어리가 가장 작은 수
• 마이너스 뒤에 만들어지는 덩어리가 가장 큰 수가 됨

각 덩어리를 앞에서부터 차례대로 빼면 최종적으로 식에서 만들 수 있는 가장 최소의 값을 찾을 수 있음

 

1. 만들 수 있는 수 덩어리 개수

마이너스를 기준으로 왼쪽과 오른쪽으로 수가 나눠지기 때문에 식에서 마이너스 연산자를 찾아 마이너스 연산자의 개수 + 1만큼 배열을 생성한다.

• sum 배열에 만들어지는 각 수의 덩어리의 합을 저장

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
		
int minusCnt = 0; // 마이너스 연산자 수 카운팅
for(int i=0; i<str.length(); i++) {
	if(str.charAt(i)=='-') minusCnt++;
}

int[] sum = new int[minusCnt+1]; // 마이너스 연산자 수 +1 만큼 배열 생성

 

2. 수 덩어리 별로 합 구하기

문자열을 한 character씩 잘라서 확인

• 숫자이면
  • 0일 경우 :: 문자열의 길이가 0이 아니면 문자열에 더하기 >> 0이 뒤에 나올 때만 숫자로 생각
  • 0이 아닐 경우 :: 문자열에 더해 숫자 만들기
• 연산자이면
  • 현재 덩어리 합에 지금 숫자 더하기
  • 숫자 만드는 문자열 초기화
  • 연산자가 마이너스(-)이면 다음 덩어리로 index 증가

int index=0; // 현재 덩어리의 index
String num="";
for(int i=0; i<str.length(); i++) {
	char ch = str.charAt(i);
			
	if(ch !='-' && ch !='+') { // 숫자일 때
		if(ch=='0') {
			if(num.length()!=0) num += ch; // 0이 앞이 아닐 때만 추가
		}
		else {
			num += ch;
		}
	}
	else { // 연산자 일 때
		sum[index] += Integer.parseInt(num); // 현재 덩어리 합에 만들어진 숫자 더하기
		num = "";
		if(ch == '-') index++; // 다음 덩어리로 넘어가기
	}
}
sum[index] += Integer.parseInt(num); // 마지막 숫자 더하기

 

3. 결과 구하기

아직 진행하지 않은 연산은 마이너스 밖에 없기 때문에 배열의 처음부터 끝까지 마이너스 연산 진행

int ans = sum[0];
for(int i=1; i<sum.length; i++) {
		ans -= sum[i];
}

 

전체 코드

package Day_0307;

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

public class B1541 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		int minusCnt = 0; // 마이너스 연산자 수 카운팅
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i)=='-') minusCnt++;
		}
		
		int[] sum = new int[minusCnt+1]; // 마이너스 연산자 수 +1 만큼 배열 생성
		int index=0;
		String num="";
		for(int i=0; i<str.length(); i++) {
			char ch = str.charAt(i);
			
			if(ch !='-' && ch !='+') { // 숫자일 때
				if(ch=='0') {
					if(num.length()!=0) num += ch; // 0이 뒤에 나오는 경우만 숫자 문자열에 추가
				}
				else {
					num += ch;
				}
			}
			else { // 연산자 일 때
				sum[index] += Integer.parseInt(num); // 현재 인덱스의 sum배열에 숫자 더하기
				num = ""; // 숫자 문자열 초기화 >> 연산자 다음은 무조건 새로운 숫자이기 때문에
				if(ch == '-') index++;
			}
		}
		
		sum[index] += Integer.parseInt(num); // 마지막 숫자 더하기
		int ans = sum[0];
		for(int i=1; i<sum.length; i++) {
			ans -= sum[i];
		}
		System.out.println(ans);
		br.close();
	}

}