[백준] 1541 : 잃어버린 괄호 - JAVA

🙋🏻‍♀️그리디 알고리즘

문제 분석

그리디 관점에서 생각하면 쉽게 풀 수 있다.
결과를 최솟값으로 만들기 위해서는 가능한 한 큰 수를 빼야한다.
덧셈, 뺄셈 연산만으로 이루어져있기때문에, 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 뺄셈을 실행한다.

슈도코드

String input 입력받기
"-"기호 기준으로 split()수행, String minus 배열에 값 넣기
String[] plus
for(minus 크기만큼 반복) {
	if(원소에 "+"기호가 없다면) plus배열에 그대로 넣기 
	"+"기호로 split() 
    나눠진 두 수를 더헤서 plus 배열에 넣기 
}
for(plus 배열 크기만큼 반복) {
	각 원소를 빼기 
}

아이디어가 생각나지 않아서, 처음에는 찾아봤다.
처음에는 '-'를 기준으로 split 하는것을 아이디어로 얻었다.

Troubleshooting

public class lostedBracket {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		String[] minus = input.split("-");
		int[] plus = new int[minus.length];
		int difference = 0;
		for(int i=0; i< minus.length; i++) {
			if(!minus[i].contains("+")) {
				plus[i] = Integer.parseInt(minus[i]);
				continue;
			}
			String[] temp = minus[i].split("+");
		    int sum = Integer.parseInt(temp[0])+ Integer.parseInt(temp[1]);
		    plus[i] = sum;
		}
		for(int i=0; i<plus.length -1; i++) {
			difference = plus[i] - plus[i+1];
		}
		System.out.println(difference);
	}
}

문제

원인

이 오류는 + 가 특별한 의미로 쓰이기 때문이다.

• 기호 말고도 * 과 ^ 으로 나눌 때도 마찬가지 입니다.

정상적으로 동작하기 위해서는 "+" 앞에 \ 를 붙여주면 됩니다.

참고사이트
https://donghyeon.dev/java/2019/06/05/Dangling-meta-character-%27+%27-near-index-0-해결/

해결

+ -> \\+ 수정

Troubleshooting 2

문제

'틀렸습니다'를 받았다.
예제 1은 답이 잘 나오나, 예제 2의 답이 0으로 나온다.

원인

1. 처음에 '-'기준으로 나눌 때, 꼭 두 수와 "+"기호 1개가 합쳐진 문자열만 생성되지는 않는데, 그렇게 생각해서 로직을 짰다.
   예제 2를 보면 알 수 있듯이, '10+20+30+40' 이렇게 한 문자열에 +와 숫자가 많을수도있다.

2. difference를 처음에 0으로 초기화하고, 마지막에 difference -= plus[i]를 수행하면 예제 2같은경우는 '-100'으로 결과가 출력된다.

해결

1. 원소가 2개만 있을거라고 단정하지않고, temp배열의 크기만큼 돌며, 차례대로 더했다.
2. difference를 plus[0]의 값으로 초기화했다.

Troubleshooting 3

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		String[] minus = input.split("-");
		int[] plus = new int[minus.length];
		int sum = 0;
		for(int i=0; i< minus.length; i++) {
			if(!minus[i].contains("+")) {
				plus[i] = Integer.parseInt(minus[i]);
				continue;
			}
			String[] temp = minus[i].split("\\+");
			for(int j =0; j<temp.length; j++) {
				sum += Integer.parseInt(temp[j]);
			}
		    plus[i] = sum;
		}
		int difference = plus[0];
		if(plus.length > 1) {
			for(int i=1; i<plus.length; i++) {
				difference -= plus[i];
			}
		}
		System.out.println(difference);
	}
}

문제

'틀렸습니다'를 받았다.

원인

sum을 초기화하지않아서, 계속 누적되는것이 문제였다!

해결

sum을 사용하고나서, 다음 사용전에 초기화했다.

---

제출 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		String[] minus = input.split("-");
		int[] plus = new int[minus.length];
		int sum = 0;
		for(int i=0; i< minus.length; i++) {
			if(!minus[i].contains("+")) {
				plus[i] = Integer.parseInt(minus[i]);
				continue;
			}
			String[] temp = minus[i].split("\\+");
			for(int j =0; j<temp.length; j++) {
				sum += Integer.parseInt(temp[j]);
			}
		    plus[i] = sum;
		    sum =0;
		}
		int difference = plus[0];
		for(int i=1; i<plus.length; i++) {
			difference -= plus[i];
		}
		System.out.println(difference);
	}
}

공부한 사항

• split()

str1 = "asdf-asdfa";
String[] str = str1.split("-");

위처럼 코드를 사용하면, split()과 동시에 String배열 str에 "-"를 기준으로 나눠진 값들이 자동으로 들어간다.

헷갈렸던 부분

• 컴퓨터는 000N도 N이라고 인식하나..?
  숫자 앞이 0일경우를 처리해야할지 말아야할지 고민이었다.
  -> 처리안해도 결과가 잘 나오긴하네.