[BOJ 1541] 잃어버린 괄호 - JAVA

오늘 풀어본 문제는 그리디 문제인 잃어버린 괄호 문제입니다.

 

한가지만 생각해낸다면,, 쉽게 풀리는 문제지만 그게 쉽지 않다는......

이 한 가지는 나중에...구현방법에서 알려줄거에여....

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

구현 내용

 

구현 방법

가장 중요한 방법 한 가지만 알아낸다면 쉽게 풀리는 문제입니다.

 

'-'가 나온 이후 모든 숫자는 -값이 될 수 있다는 것입니다. 

ex)

55-40+35 => 55-(40+35)

40-30+35+40-10+10 => 40-(30+35+40)-(10+10)

 

이런식으로 첫 '-'가 나온 이후 값들은 전부 -값으로 만들 수 있습니다.

그래서 '-' 가 나온 이후 값들은 전부 빼고 그전 값들은 전부 더하면 문제는 쉽게 풀립니다.

만약 '-' 가 나오지 않는 다면 전부 더하면 됩니다.

 

자세한 설명은 주석을 통해 해드리겠습니다.

 

 

↓↓↓↓↓↓↓↓↓↓↓↓↓      ↓↓↓↓↓↓↓↓↓↓↓↓↓        ↓↓↓↓↓↓↓↓↓↓↓↓↓↓

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 출력
        String line = br.readLine();
        int h = 1;          //숫자의 위치
        int result = 0;     //결과 값
        Queue<String> q = new LinkedList<>();       //부호
        String num[] = line.split("\\+|-");   //숫자 배열
        for(int i=0;i<line.length();i++){           //+ -를 부호 큐에 담기
            if(line.charAt(i)=='-')
                q.offer(String.valueOf(line.charAt(i)));
            else if(line.charAt(i)=='+')
                q.offer(String.valueOf(line.charAt(i)));
        }
        result = Integer.parseInt(num[0]);  //가장 처음 숫자를 result에 대입한다.
                                            // 가장 처음엔 부호가 나오지 않기 때문
        while(!q.isEmpty()){                // 큐에 데이터가 있다면
            if(q.poll().equals("-")){       // 가장 처음 -가 나올때 까지 q를 돈다
                break;
            }
            else{                           //-가 나오기 전에 숫자들은 더한다
                result += Integer.parseInt(num[h]);
                h++;
            }
        }
        for(int i=h;i<num.length;i++){      // -가 나온 이후 숫자들은 전부 - 값으로
                                            // 만들 수 있기 때문에  result 값에서 -가
                                            // 나온 이후 값들은 전부 뺸다
            result -= Integer.parseInt(num[i]);
        }
        bw.write(String.valueOf(result));
        bw.flush();
    }
}