[BOJ] 1541 - 잃어버린 괄호 (Java)

알고리즘

• 수학
• 그리디 알고리즘
• 문자열
• 파싱

1. 문제

2. Idea

• 최솟값을 만드는 방법: 덧셈 부분을 먼저 계산 하는 것
• 문자열을 분리해주는 split() 함수나 StringTokenizer 클래스 사용

1. 뺄셈(-)을 기준으로 1차적으로 문자열을 분리해준다.

2. 분리된 문자열들 각각에 포함 된 정수 값들을 모두 더 해준다.

3. 각각 더해진 값들을 뺄셈해준다.

   

• 뺄셈기호(-)를 중심으로 먼저 문자열을 분리해준 뒤, 각 분리된 문자열안에 있는 정수끼리 더해준다. 그 후, 분리된 문자열들을 뺄셈 연산

• '첫 번째 수는 양수'라는 점 유의

3. 풀이

3.1. 입력 및 초기화

• 뺄셈 기호를 기준으로 수식을 나누기 위해 StringTokenizer를 사용

int sum = Integer.MAX_VALUE; // 초기 상태 여부 확인을 위한 값으로 설정
StringTokenizer subtraction = new StringTokenizer(in.nextLine(), "-");

3.2. 수식 계산 및 결과 출력

• 뺄셈으로 나뉜 각 토큰을 덧셈으로 분리하고, 해당 토큰들을 모두 더한 뒤, 각 부분의 합을 이전에 계산한 결과(sum)에서 뺀다.
• 이런 식으로 모든 뺄셈 부분에 대해 반복하면 최종적으로 최소의 값이 계산된다.

while (subtraction.hasMoreTokens()) {
    int temp = 0;

    // 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
    StringTokenizer addition = new StringTokenizer(subtraction.nextToken(), "+");

    // 덧셈으로 나뉜 토큰들을 모두 더한다.
    while (addition.hasMoreTokens()) {
        temp += Integer.parseInt(addition.nextToken());
    }

    // 첫 번째 토큰인 경우 temp 값이 첫 번째 수가 됨
    if (sum == Integer.MAX_VALUE) {
        sum = temp;
    } else {
        sum -= temp;
    }
}

System.out.println(sum);

4. 전체코드

import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
		StringTokenizer subtraction = new StringTokenizer(in.nextLine(), "-");
 
		while (subtraction.hasMoreTokens()) {
			int temp = 0;
 
			// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
			StringTokenizer addition = new StringTokenizer(subtraction.nextToken(), "+");
			
			// 덧셈으로 나뉜 토큰들을 모두 더한다. 
			while (addition.hasMoreTokens()) {
				temp += Integer.parseInt(addition.nextToken());
			}
			
			// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
			if (sum == Integer.MAX_VALUE) {
				sum = temp;
			} else {
				sum -= temp;
			}
		}
		System.out.println(sum);
	}
 
}