안정적인 문자열 - 백준 4889 (Java)

https://www.acmicpc.net/problem/4889

 

풀이

1. { 는 stack에 넣는다.

2. } 일 때는, stack이 비어있을 때는 count+1을 하고 { 로 바꿔서 stack에 넣어준다.

    stack이 비어있지 않을 때에는 stack에 저장된 { 을 pop하여 짝을 짓는다.

3. 모든 과정을 마친 후, stack에 남은 { 의 갯수의 절반을 count에 더해준다. 4개가 남았다면 2개를 } 로 바꿔주면 안정적인 문자열이 되기 때문이다. 즉, stack이 empty하게 만드는 것이다.

 

count()

private static int count(Stack<Character> stk, String str) {
    int answer = 0;
    int length = str.length();

    for (int i = 0; i < length; i++) {
        char now = str.charAt(i);

        switch (now) {
            case '{' :
                stk.push(now);
                break;
            case '}' :
                if (stk.isEmpty()) {
                    answer++;
                    stk.push('{');
                } else {
                    stk.pop();
                }//if~else end
                break;
        }//switch case end
    }//for end

    int left = stk.size();
    answer += (left / 2);

    return answer;
}//count() end

 

main()

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    Stack<Character> stk = new Stack<>();
    StringBuilder sb = new StringBuilder();

    int index = 1;

    while (true) {
        String str = bf.readLine();

        if (str.contains("-")) {
            break;
        }//if end

        //stack 초기화
        stk.clear();

        int count = count(stk, str);

        sb.append(index)
            .append(". ")
            .append(count)
            .append("\n");

        index++;
    }//while end

    System.out.println(sb);
}

 

 

 

** stack을 사용하지 않고 그냥 { 의 개수만 가지고 해도 된다.

 

private static int count(String str) {
    int answer = 0;
    int length = str.length();

    int num = 0;

    for (int i = 0; i < length; i++) {
        char now = str.charAt(i);

        switch (now) {
            case '{' :
                num++;
                break;
            case '}' :
                if (num==0) {
                    answer++;
                    num++;
                } else {
                    num--;
                }//if~else end
                break;
        }//switch case end
    }//for end

    answer += (num / 2);

    return answer;
}//count() end