[인프런 알고리즘] Chapter 5, 2번 문제(괄호문자제거)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

첫 번째 코드(스택 이용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class sec05_02 {
    public static String solution(String str)
    {
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for(char c : str.toCharArray())
        {
            if(c == ')') while(stack.pop() != '(');
            else stack.push(c);
        }

        for(int i = 0; i < stack.size(); ++i) sb.append(stack.get(i));
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(solution(br.readLine()));
    }
}

 

두 번째 코드(스택 이용 X)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sec05_02 {
    public static String solution(String str)
    {
        StringBuilder sb = new StringBuilder();
        int left = 0;
        for(char c : str.toCharArray())
        {
            if(c == '(') ++left;
            else if(c == ')') --left;
            else if(left == 0) sb.append(c);
        }
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(solution(br.readLine()));
    }
}

 

설명

두 번째 코드에 대한 설명

solution 메서드는 문자열에서 괄호로 둘러싸인 부분을 제거하고, 남은 문자열을 반환하는 기능을 한다. 주어진 문자열에서 괄호 내부의 문자는 무시하고, 괄호 외부의 문자들만을 추출하여 결과 문자열을 만든다.

• int left = 0; -> 여는 괄호의 수를 추적하기 위한 변수 left를 초기화한다.
• for(char c : str.toCharArray()) ->문자열 str을 문자 배열로 변환하고, 각 문자를 순차적으로 확인한다.
• if(c == ‘(’) ++left; -> 현재 문자가 여는 괄호 ’(’인 경우, left를 1 증가시킨다.
• else if(c == ‘)’) –left; -> 현재 문자가 닫는 괄호 ’)’인 경우, left를 1 감소시킨다.
• else if(left == 0) sb.append(c); -> 현재 문자가 여는 괄호도 닫는 괄호도 아닌 경우, 그리고 left가 0일 때만 sb에 현재 문자를 추가한다. left가 0인 경우는 현재 문자가 괄호 밖에 있다는 의미이다.