[백준] 단계별로 풀어보기(단계:16,그리디 알고리즘,JAVA)1541번, 잃어버린 괄호

문제 링크

1541번: 잃어버린 괄호

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그리드 알고리즘(탐욕 알고리즘)이란 여러 경우를 선택해야할 때 그 상황에 최적의 경우으로 생각하는 것을 반복하여 최종적인 답을 가져오는 방법입니다.

 

이 문제에서 최소로 만드려면 '-' 이후에 값들을 모두 더하면 됩니다.

예를 들어 20 + 40 - 30 + 20 - 20 + 40이면 20 + 40 - (30+20) - (20+40) = -50이 최소값이 됩니다.

그래서 입력값을 '-' 기준으로 나눈 뒤 '+'가 존재하면 '+' 기준으로 숫자를 나누어 더하였습니다.

첫 '-'가 나오기 전까지는 빼지지 않고 더하기 때문에 기본값으로 설정할 수 있습니다. 그래서 기본값을 저장하기 전에 나올 수 없는 숫자 Integer.MIN_VALUE로 지정한 뒤 if문을 사용하여 동일한 숫자이면 기본값을 저장하도록 하였습니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 '-'와 '+'로 나누어서 구한다.
• while문을 사용하여 StringTokenizer에 다음 토큰이 있는지 확인하도록 하여 반복하였습니다.
• 첫 '-'가 나오기 전에 빼지지 않고 기본값을 설정하도록 if문을 사용하였습니다.
• BufferedWriter을 사용하여 최소값을 출력하였습니다.

결과 코드

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));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //--------입력값 저장-----------
    	int sum = Integer.MIN_VALUE;	//결과값
    	StringTokenizer st1 = new StringTokenizer(br.readLine(),"-");
    	while(st1.hasMoreTokens()) {
    		int temp = 0;
    		StringTokenizer st2 = new StringTokenizer(st1.nextToken(),"+");
    		while(st2.hasMoreTokens()) {
    			temp += Integer.parseInt(st2.nextToken());
    		}
    		if(sum == Integer.MIN_VALUE)	//'-'이전 연산
    			sum = temp;
    		else		//'-'이후 연산
    			sum -= temp;
    	}
    	
    	
    	bw.write(sum + "\n");	//결과 출력
    	bw.flush();
    	bw.close();
    	br.close();
	}
}