[알고리즘풀이]백준 1541: 잃어버린 괄호 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 1541번 잃어버린 괄호를 풀었습니다. 이를 정리해보고자 합니다.

1541번: 잃어버린 괄호

 

본문

1) 문제

 

2) 과정

이 문제는 좀 어려워서 오래 걸렸던 문제입니다...! 특히 split이 되지않아서 어려워했던 문제입니다. (그 해답은 2-3) Logic을 확인해주세요)

 

2-1) main

    // Attribute
    private static int answer; // 정답
    private static String expression; // 식
    
    // Main
	public static void main(String[] args) throws IOException {
        input();
        func();
        System.out.println(answer);
    }

main은 input과 func, 출력 부분으로 구성하였습니다. 각각은 아래 나올 내용의 Input, Logic과 출력문 System.out.println(answer);입니다. 모든 계산이 마치게 되면 최소값인 answer이 출력되며 실행이 종료됩니다.

 

전역변수로 선언한 사용할 변수 answer, expression은 각각 식의 값을 최소로 만들었을 때의 값, 표현식입니다.

 

2-2) Input

    public static void input() throws IOException{
        // Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        expression = reader.readLine();
    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

첫번째 줄을 읽어 주어진 식을 expression에 넣어줍니다.

 

2-3) Logic

    private static int calculator(String subExp) {
        int retVal = 0;
        String[] splitedExp = subExp.split("\\+");
        for(String s:splitedExp) retVal+=Integer.parseInt(s);
        return retVal;
    }

    public static void func(){
        String[] splitedExp = expression.split("-");
        for(int i=0;i<splitedExp.length;i++){
            int subExp = calculator(splitedExp[i]);
            if(i==0) answer=subExp;
            else answer-=subExp;
        }
    }

func()가 불리면, -를 기준으로 식을 나눠줍니다. 그리고 이를 하나씩 calculator로 보내 +마다 그 합을 구해준 뒤 return을 해줍니다. split에 +가 아닌 \\+가 들어있는 이유는 +를 기준으로 split을 한다고하면 컴파일러가 이를 인식하지 못하여 에러가 발생하기 때문입니다. 이 부분 때문에 꽤 고생했습니다. 제가 참고했던 사이트 링크는 아래와 같습니다.

JAVA 특수문자 split

 

다시 func로 돌아와 이어서 설명을 하면 -(+로 묶인 덩어리 값) - (+로 묶인 덩어리값)으로 묶었을 때 가장 작은 경우가 나오기 때문에 가장 맨 앞의 덩어리는 subExp자체를 answer에 넣어주고, 그 이후에는 answer에 subExp(+로 묶인 덩어리값들)을 빼주며 모든 식을 방문합니다.

 

이를 모두 마치면 answer에 입력받은 식으로 만들 수 있는 가장 작은 값이 들어있게 되고 이를 main에서 출력하며 실행은 종료됩니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class BOJ1541 {

	private static int answer; // 정답
    private static String expression; // 식

    public static void input() throws IOException{
        //input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        expression = reader.readLine();
    }

    private static int calculator(String subExp) {
        int retVal = 0;
        String[] splitedExp = subExp.split("\\+");
        for(String s:splitedExp) retVal+=Integer.parseInt(s);
        return retVal;
    }

    public static void func(){
        String[] splitedExp = expression.split("-");
        for(int i=0;i<splitedExp.length;i++){
            int subExp = calculator(splitedExp[i]);
            if(i==0) answer=subExp;
            else answer-=subExp;
        }
    }


    public static void main(String[] args) throws IOException {
        input();
        func();
        System.out.println(answer);
    }
}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/greedy/BOJ1541.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비