[그리디 알고리즘-Java] 1541번 잃어버린 괄호

 

 

1. 그리디 알고리즘이란?

 

탐욕스런 알고리즘이다. 미래를 생각하지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 것이다. 때문에 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다.

 

 

2. 그리디 알고리즘이 최적의 답을 갖는 문제는?

 

1) 문제의 일부분에서 전체의 해답을 찾을 수 있는 경우

 

2) 다이나믹 프로그래밍처럼 모든 부분을 고려하는 것이 아닌 탐욕적 선택만 하더라도 최적인 답을 찾을 수 있는 경우

 

예를 들면 거스름돈을 가장 적게 거슬러주는 문제가 있다.

 

 

그리디 알고리즘 참고 문서 : https://seungjuitmemo.tistory.com/23

알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자!

 

 

3. 1541번 잃어버린 괄호 - 문제 해석 (생각의 흐름)

 

1541번: 잃어버린 괄호

 

 

 

1) 제약사항

1) 0~9을 가지고 수를 만든다. 수는 5자리보다 많이 연속되는 숫자는 없다.

2) 수는 0으로 시작할 수 있다. -> 0 제거 필요

3) 부호는 + , - 두 가지만 나온다.

4) 총 식의 길이는 50보다 작거나 같다.

5) 5 + + 2 와 같이 연산자가 연속해서 나타나지 않는다.

 

 

 

5) 최소값을 만들어야 하기 때문에 최대한 -를 크게 만드는 것이 요건이다. -> 첫번째 -가 등장하면 다음 마이너스가 나올 때 까지 괄호쳐줄 것이다.

 

 

4. 자바 코드

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//1. 식을 입력 받는다.
		//2. 마이너스 기준으로 split한다. (- 없어짐)
		String[] sentence = sc.nextLine().split("\\-");
		//3. index별로 더해줄 건 더해주기 
		int[] index_total = new int[sentence.length]; //index 별로 더한 값을 저장할 리스트 
		
		for(int i=0;i<sentence.length;i++) {
			//4. 숫자와 + 구분 (+는 없어짐)
			if(sentence[i].contains("+")) {
				//4-1. 만약 + 부호가 있으면 +로 구분하고 숫자로 변환하는 과정 필요 
				//\\표시 없으면 java.util.regex.PatternSyntaxException 뜸.  
				String[] sperate_plus = sentence[i].split("\\+");
				//5.모두 숫자로 바꿔 더해주기 
				for(int j=0;j<sperate_plus.length;j++) {
					//0009도 (int)로 형바꿈하면 에러나지만 Integer.parseInt("0009");로 하면 형바꿈 잘된다.
					index_total[i] += Integer.parseInt(sperate_plus[j]);
				}
			}
			else {
				//4-2. + 부호가 없으면 그냥 숫자로 변환하기 
				//0009도 (int)로 형바꿈하면 에러나지만 Integer.parseInt("0009");로 하면 형바꿈 잘된다.
				index_total[i]=Integer.parseInt(sentence[i]);
			}
				
		}
		//index 0번째 값은 초기에 들어가고, 1번 index부터 빼줄 것 
		int result=index_total[0];
		//6. 최종 인덱스별 합들을 마이너스해주기 
		for(int i=1;i<index_total.length;i++) {
			result-=index_total[i];
		}
		
		//7. 결과 출력
		System.out.println(result);
	}

}

 

 

5. 새로 알게 된 것들

 

1. java.util.regex.PatternSyntaxException : Dangling meta character '+' near index 0

String[] sentence = sc.nextLine().split("\\-");
String[] sperate_plus = sentence[i].split("\\+");

 

+나 - 등 특수기호로 split을 할 때 \\ 표시를 꼭 붙여줘야 exception이 나지 않는다.

 

 

2. 0009 int로 형변환

int num = (int)"0009"; //error!
int num = Integer.parseInt("0009"); //ok!

(int)로 형변환하면 안되고, Integer.parseInt로 형변환해야한다.