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

문제

---

1541번: 잃어버린 괄호

접근법

---

예제 1부터 살펴보자

55-50+40 ⇒ 55-(50+40) 로 계산해야 최적해가 나온다.

그렇다면, -보다 +를 항상 먼저 계산하면 되는가?

55+50-40 일때 + 를 먼저 계산한다고 해서 값이 작아지지 않는다.

‘-’ 뒤에 나오는 수의 절댓값을 가장 최대로 만들어야 한다!!

→ ‘-’ 뒤에 나오는 모든 ‘+’ 들을 먼저 연산한다.

자료형은 어떻게 사용할까?

1. 숫자와 연산자를 따로 저장
   • 연산자 배열의 인덱스를 확인
   • 연산자의 인덱스와 같은 인덱스는 원래 식에서 연산자 앞에 있는 숫자
   • 연산자의 인덱스보다 1 큰 인덱스는 원래 식에서 연산자 뒤에 있는 숫자
   → 너무 번거로움
2. StringTokenizer로 ‘-’ 단위로 끊어서 계산
   • Token 자체가 괄호 역할을 해버림
   → 굿!

풀이

---

풀이 1: '-' 뒤에 나오는 '+'를 괄호로 묶어서 풀기

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int sum = 0;

        //아예 처음부터 -가 없는 경우
        if (!line.contains("-")) {
            int dummy = getDummy(line);
            sum += dummy;
            System.out.println(sum);
            return;
        }

        StringTokenizer parentheses = new StringTokenizer(line, "-", true); //괄호단위
        boolean negative_flag = false;

        while (parentheses.hasMoreTokens()) {
            String s = parentheses.nextToken();

            if (s.equals("-")) {
                negative_flag = true;
                continue;
            }

            if (s.contains("+")) { //괄호 계산

                int dummy = getDummy(s); //+ 포함하는 괄호 안 구하는 메서드

                if (negative_flag) { //음수 뒤에 오는 괄호만 빼기
                    sum -= dummy;
                } else { //음수 뒤에 오지 않는 수는 더하기
                    sum += dummy;
                }

            } else { //괄호 없을때
                int abs = Integer.parseInt(s);
                if (negative_flag) { //음수일 경우
                    abs *= -1;
                }

                sum += abs;
                negative_flag = false;
            }


        }
        System.out.println(sum);
    }

    private static int getDummy(String s) {
        StringTokenizer st = new StringTokenizer(s, "+");
        int dummy = 0;
        while (st.hasMoreTokens()) {
            int i = Integer.parseInt(st.nextToken());
            dummy += i;
        }
        return dummy;
    }
}

 

 

트러블슈팅

---

이슈 1

• 문제
  • 위의 방법에서 flag를 사용하지 않으면 앞에 '-'가 오는지  '+'가 오는지 모르기 때문에 00009-00009를 18로 답을 내버린다.
• 원인
  • 숫자를 token 별로 분리를 하더라도 음수로 처리할 것인지 양수로 처리할 것인지 표시를 해두지 않아서 괄호가 필요 없는 경우에서 문제가 발생
• 해결
  • flag를 표시하는 방법을 선택!

-> 어차피 flag를 표시할꺼면 진작부터 경우를 모두 나눠줄 필요 없이 '-'가 나온 순간부터 뒤의 나오는 모든 수들을 빼주면 되는거 아닌가?

 

풀이 2: ‘-’가 나오는 순간부터 나오는 모든 수들을 그냥 빼준다 (그전까지는 더해줌)

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();

        int sum = 0;

        StringTokenizer parentheses = new StringTokenizer(line, "-", true); //괄호단위
        boolean negative_flag = false;

        while (parentheses.hasMoreTokens()) {
            String s = parentheses.nextToken();

            if (s.equals("-")) { //-가 나오는 순간을 확인! -> flag를 바꿔줌
                negative_flag = true;
                continue;
            }

            StringTokenizer st = new StringTokenizer(s, "+");
            while (st.hasMoreTokens()) {
                int i = Integer.parseInt(st.nextToken());

                if (negative_flag) { //-가 이미 나왔으면 모두 빼버림
                    sum -= i;
                } else { //-가 아직 안나온 상태이므로 더함
                    sum += i;
                }
            }
        }

        bw.write(String.valueOf(sum));
        bw.flush();
    }
}

---

이슈 2

• 문제
  • StringTokenizer에서 - 단위로 끊을 때 Token이 ‘-’뒤에 나오는 token인지 아닌지를 판별해야 함
• 원인
  • StringTokenizer를 하면 구별자는 빠져서 token에 들어감
• 해결
  • StringTokenizer의 생성자의 3번째 인자로 true를 설정.

//1. 띄어쓰기 기준으로 문자열을 분리
StringTokenizer st = new StringTokenizer(대상 문자열); 

//2. 구분자를 기준으로 문자열을 분리
StringTokenizer st = new StringTokenizer(대상 문자열, 구분자); 

// 3. true -> 구분자를 기준으로 문자열을 분리할 때 구분자도 토큰으로 넣는다.  
// false -> 구분자를 분리된 문자열 토큰에 포함 시키지 않는다. 
// (디폴트 : false)  
StringTokenizer st = new StringTokenizer(대상 문자열 , 구분자 , true/false);

• 예시)

import java.util.StringTokenizer;

publi class Main {
		public static void main(String[] args) {
				String str = "55+40-20"
				StringTokenizer st = new String Tokenizer(str, "-", true);	
			
				while(st.hasMoreTokens()){
						System.out.println(st.nextToken());
				}
		}
}

55+40
-
20

• 레퍼런스
  • https://dev-coco.tistory.com/94