[백준] 1541번 : 잃어버린 괄호 – JAVA [자바]

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

 

 

---

문제

---

문제 풀이

문제 해결 방법:

1. '-'를 기준으로 나누기
'-' 연산자는 큰 숫자를 빼는 것이므로, 이를 기준으로 나누면 최솟값을 만들기 쉬워진다.

2. 각 그룹의 숫자를 더하기
'-'를 기준으로 나눈 각 부분은 '+' 연산자로 연결된 숫자 그룹이다. 따라서, 각 그룹을 먼저 더한다.

 

3. 첫 번째 그룹을 시작값으로 설정하고 나머지 그룹을 빼기
첫 번째 그룹은 그대로 사용하고, 이후의 그룹들은 모두 빼주면 된다.

---

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        
        // '-' 기준으로 나누기
        String[] parts = input.split("-");
        
        // 첫 번째 그룹은 더하고 시작
        int total = addAll(parts[0]);
        
        // 이후의 그룹들은 모두 빼기
        for (int i = 1; i < parts.length; i++) {
            total -= addAll(parts[i]);
        }
        System.out.println(total);
    }

	// '+' 연산자로 연결된 숫자들을 모두 더하는 함수
    public static int addAll(String s) {
        StringTokenizer st = new StringTokenizer(s, "+");
        int total = 0;
        while (st.hasMoreTokens()) {
            total += Integer.parseInt(st.nextToken());
        }
        return total;
    }

}

 

 

---

시간 복잡도 분석

split("-")는 O(N), StringTokenizer를 이용한 덧셈 연산도 O(N)

따라서 전체 시간 복잡도는 O(N)