[스택] 2. 괄호문자제거

2. 괄호문자제거

 

설명

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.

입력

첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.

출력

남은 문자만 출력한다.

예시 입력 1 

(A(BC)D)EF(G(H)(IJ)K)LM(N)

예시 출력 1

EFLM

 

 

<<풀이>>

 

-나의 풀이-

 

시간복잡도 : O(N)

 

우선 이 문제는 Stack 자료구조를 이용하면 수월하게 풀 수 있다.

 

'(' 이 시작이 되면 cnt는 1을 더하고, ')'가 있으면 cnt에 1을 뺀다. 이렇게 돌다가

 

cnt = 0 이 되는 시점 부터 stack에다가 넣어준다.

 

Stack은 LIFO 형태이므로, 이를 고려하여 answer에 문자를 더하는 구조를 짜서 정답을 도출했다!

 

import java.util.Scanner;
import java.util.Stack;

class Main {
    private String solution(String n) {
        Stack<Character> stack = new Stack<>();
        int cnt = 0;
        for(char x : n.toCharArray()) {
            if(x == '(') cnt++;
            else if (x == ')') cnt--;
            else if (cnt == 0) stack.push(x);
        }
        int stackSize = stack.size();
        String answer = "";
        for(int i = 0; i < stackSize; i++) {
            answer = stack.pop() + answer;
        }

        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String n = in.next();
        System.out.println(T.solution(n));
    }
}

 

-강사님 풀이-

 

import java.util.Scanner;
import java.util.Stack;

class Main {
    private String solution(String str) {
        String answer = "";
        Stack<Character> stack = new Stack<>();
        for (char x : str.toCharArray()) {
            if (x == ')') {
                while (stack.pop() != '(');
            } else stack.push(x);
            }
            for (int i = 0; i < stack.size(); i++) answer += stack.get(i);
            return answer;
        }


        public static void main (String[]args){
            Main T = new Main();
            Scanner in = new Scanner(System.in);
            String str = in.next();
            System.out.println(T.solution(str));
        }
    }

 

강사님은 나랑 같은 자료구조 Stack을 활용했지만, 조금 다른 방식으로 접근했다. 

 

우선 전체적인 흐름은 값을 돌면서 stack에 넣다가 ) 이 나오면 ( 나오기 까지 pop한다 ! 그런식으로 해서 최종적으로 남는 것을 answer에 더하면서 값을 도출한다.

 

특징은 

 

 answer += stack.get(i);

 

나는 여태껏 Stack 메서드에는 get()없는 줄 알았다. 근데 get이 있었고 이러면 굳이 stack의 특성 LIFO를 생각 안 하고 값을 추출할 수 있다 !

 

또한, 

 

while (stack.pop() != '(');

 

이를 활용하면, ( 이값이 나오기까지 pop을 시키는데 어 그러면  마지막  ( 은 제거 안되는 것이 아닌가?? 하지만 사실상 pop하고나서 비교하기 때문에 이미 없는 상황이 된다!! 이런 점을 잘 파악하자 ~~