[Java] 백준 1541번 [잃어버린 괄호] 자바

: ) YOUNG·2022년 4월 13일
Javaalgorithm문자열백준
2

알고리즘

목록 보기
96/422
post-thumbnail

백준 1541번
https://www.acmicpc.net/problem/1541

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 

55-50+40

예제 출력 

-35

생각하기

문제만 봤을 때는 별로 어렵지 않은 문제같은데, 구현해보면 진짜 까다로운 부분이 많았습니다.

테스트케이스는 4개 정도를 썼는데, 기본으로 제공하는 테스트케이스 3개와

01+0-1

까지 4개의 테스트케이스를 사용하면 문제를 완벽하게 풀 수 있다고 생각합니다.

문제를 풀고나서 Greedy알고리즘인걸 알게됬는데, 다른 분들의 코드를 참고해서 다시 풀어봐야겠습니다.


동작 

		String zero = "+";
		// 처음 시작하는 부호가 -가 아닐경우 (양수일 경우)
        // +를 앞에 붙여줌
        
		if( !formula.startsWith("-")) {
			zero += formula;
			formula = zero;
		}

들어오는 테스트케이스를 먼저 formula 변수에 저장한 뒤
시작하는 문자열이 -가 아닐 경우, 즉 처음 시작이 양수로 시작할 경우
formula에 +기호를 붙여줍니다. 양수임을 판별하기 위해서 쓰입니다


		int length = formula.length();
		boolean open = false;
		for(int i=0; i<length; i++) {
			char ch = formula.charAt(i);
			
			if(ch == '-' && open == false) {
				open = !open;
				list.add(ch + "(+");
			}
			// + 기호 인데, 괄호가 열려있음을 의미
			else if(ch == '+' && open == true) {
				list.add(String.valueOf(ch));
			}
			else if(ch == '-' && open == true) {
				list.add(")" + ch + "(+");
			}
			else {
				list.add(String.valueOf(ch));
			}
			
			// 마지막줄에 괄호가 열려있을 경우
			if( i == length-1 && open == true) {
				list.add(")");
			}
		}

먼저 설명에 앞서 가장위에 List<String>를 생성해뒀습니다.
이유는 식을 수정할건데, 수정할 식의 길이가 어떻게 될지 모르기 때문에 동적할당을 위해서 list를 만들었습니다. 이 list에 새로운 식을 넣을겁니다.

식의 길이 만큼 반복하기 위해 length 변수를 만듭니다.
여기서 for문 안에 formula.length() 를 직접 넣으면 되는데, 왜 굳이length 변수를 만들어서 쓰시냐고 궁금하실수도 있는데, for문안에 length함수를 넣게되면,

for문이 반복되는 동안 i값과 비교하기 위해서 계속해서 formula.length()를 호출하게됩니다. 반복이 적으면 상관없지만, 많은 양의 반복에서는 굉장히 비효율적이기때문에 for문안에서 length함수를 사용하는 것은 추천하지 않습니다.

open은 괄호가 현재 열려있는지 닫혀있는지를 판단하기 위한 변수입니다.
기본값은 괄호가 현재 열려있지 않다로 false 입니다.

이제 ch는 formula의 한글자씩 잘라서 if문으로 집어 넣습니다.

if(ch == '-' && open == false)는 -인데 괄호가 열려있지 않은 경우 입니다.
이 경우는 -부호끼리 묶어서 +로 만들어주면 되기 때문에 "-(+" 를 list에 넣어줍니다.
이렇게 하면 -(+40+30 의 모양으로 식을 만들수 있습니다. -가 시작되면서 괄호로 묶습니다.

else if(ch == '+' && open == true)는 +인데 괄호가 열려있는 경우입니다.
이 경우는 괄호를 닫지 않고 그대로 list에 집어 넣습니다. 최소값을 만들기 위한 괄호의 범위에 들어갑니다.

else if(ch == '-' && open == true)는 -인데 괄호가 열려있는 경우입니다.
이제 다음 -가 나왔기 때문에 괄호를 닫아준후 다시 괄호를 열고 +를 붙여줘야 합니다.

즉, 중간에 -가 있을 경우 입니다.
예를 들면 -40 + 30 - 20 같은 경우 입니다. 이 식은 -(+40+30)-(+20)으로 바뀝니다.

그 외의 경우 else는 식이 유지되기 위해서 그대로 list에 넣어줍니다. list가 String형 이기때문에 char형을 집어넣기 위해서는 String.valueOf()함수를 써서 넣어줘야 합니다.

가장 마지막줄인 if( i == length-1 && open == true)은 마지막에 괄호가 열려있을 때, 괄호를 닫아주기 위한 조건문입니다.


		formula = "";
		for(String str : list) {
			formula += str;
		}

이렇게 해서 list에 들어있는 식을 다시 formula 문자열로 넣습니다.

처음 식이 55-50+40 일 경우 수정하면 +55-(50+40) 형식으로 바뀝니다.


  1. 이제 마지막 계산을 하는 결과입니다.
        StringTokenizer st = new StringTokenizer(formula, "-");
        int minus_sum = 0;
        int plus_sum = 0;

        while(st.hasMoreElements()) {
            String temp = st.nextToken();

            if( temp.contains("(")) {
                temp = temp.replace("(", "");
                temp = temp.replace(")", "");

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    minus_sum -= Integer.parseInt(plus_token.nextToken());
                }

            }
            else if ( temp.contains("+")){

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    plus_sum += Integer.parseInt(plus_token.nextToken());
                }

            }
        }

        System.out.println(minus_sum + plus_sum);

음수의 합을 저장할 minus_sum과 양수의 합을 계산할 plus_sum을 만들어줍니다.

StringTokenizer st = new StringTokenizer(formula, "-");
수정된 식인 formula가 +30-(+70)-(+20+40)-(+10+100+30)-(+35) 일 경우
일단 전체를 -를 토큰으로 나눕니다.
반복하여 분리된 토큰을 저장한temp들은 아래와 같습니다.

temp : +30
temp : (+70)
temp : (+20+40)
temp : (+10+100+30)
temp : (+35)

의 temp 값들을 가질 수 있습니다.

이제 여기서 알 수 있는 점은 "("가 있는 것들은 모두 음수값이 될 거라는 점이고"("가 없는 것은 그냥 양수 값이 된다는 것입니다.

그래서 temp에 contain함수를 이용해 있는지 검사하여 true일 경우 "("가 있다로 판단합니다.

여기서 중요한 점은 if문의 순서도 중요합니다. 공통적으로 모두 +기호는 있지만, "("는 음수에만 해당하기 때문에 조건문인 if( temp.contains("("))을 먼저 주어야합니다.

이제 음수의 합을 계산하기 위해서 "(" 와 ")"를 replace함수를 통해서 제거해줍니다.

이후에 남은 +기호를 다시 토큰값으로 지정해서 정수로 끊어준 후 plus_token을 전체 순환하며 minus_sum 에 모두 합해줍니다.

	StringTokenizer plus_token = new StringTokenizer(temp, "+");
    while(plus_token.hasMoreElements()) {
              minus_sum -= Integer.parseInt(plus_token.nextToken());
    }

그 다음 else if ( temp.contains("+")){ 오로지 + 기호만 있을 경우 입니다.

이 값은 모두 양수라는 의미이기 때문에 위 처럼 +기호를 토큰으로 해서 plus_sum 합을 구해줍니다.

이렇게 하면 음수의 합과 양수의 합을 구분지어서 구할 수 있습니다.
이제 결과 값은 minus_plus 와 plus_sum을 빼주기만 하면 결과값이 됩니다.


이 문제는 생각할 부분이 적어서 다행입니다. - + ( ) 이 4가지의 경우만 생각하면 되서 이정도로 구현에 성공한 것 같습니다.

더 다양한 문자열의 경우가 있었다면, 실패할 수 있었다고 생각하기 때문에 다른 분들의 코드를 참고해서 학습이 필요할 것 같습니다.

솔직히 진짜 못 만든 코드이지만, 내가 생각한대로 구현에 성공했다는 데 의미가 있어서 기분이 좋습니다.


TMI


문자열 진짜 꼭 쉬운 문제 같은데 구현이 참 어려워
마치 길에서 아는사람을 마주쳤는데, 아 쟤 누구더라.. 하는 기분이랄까..



코드 


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

public class Main {	

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		List<String> list = new ArrayList<>();
		String formula = br.readLine();
		String zero = "+";

		// 처음 시작하는 부호가 -일 경우 (음수일 경우)
		if( !formula.startsWith("-")) {
			zero += formula;
			formula = zero;
		}


		int length = formula.length();
		boolean open = false;
		for(int i=0; i<length; i++) {
			char ch = formula.charAt(i);

			if(ch == '-' && open == false) {
				open = !open;
				list.add(ch + "(+");
			}
			// + 기호 인데, 괄호가 열려있음을 의미
			else if(ch == '+' && open == true) {
				list.add(String.valueOf(ch));
			}
			else if(ch == '-' && open == true) {
				list.add(")" + ch + "(+");
			}
			else {
				list.add(String.valueOf(ch));
			}

			// 마지막줄에 괄호가 열려있을 경우
			if( i == length-1 && open == true) {
				list.add(")");
			}
		}

		formula = "";
		for(String str : list) {
			formula += str;
		}

        StringTokenizer st = new StringTokenizer(formula, "-");
        int minus_sum = 0;
        int plus_sum = 0;

        while(st.hasMoreElements()) {
            String temp = st.nextToken();

            if( temp.contains("(")) {
                temp = temp.replace("(", "");
                temp = temp.replace(")", "");

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    minus_sum -= Integer.parseInt(plus_token.nextToken());
                }

            }
            else if ( temp.contains("+")){

                StringTokenizer plus_token = new StringTokenizer(temp, "+");
                while(plus_token.hasMoreElements()) {
                    plus_sum += Integer.parseInt(plus_token.nextToken());
                }

            }
        }

        System.out.println(minus_sum + plus_sum);

	} // End of main
} // End of class
profile
: ) YOUNG
이전 포스트

[Java] 백준 10866번 [덱] 자바

다음 포스트

[Java] 백준 1620번 [나는야 포켓몬 마스터 이다솜] 자바

0개의 댓글