[프로그래머스] 올바른 괄호

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때,
문자열 s가 올바른 괄호이면 true를 return 하고,
올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

내 풀이

//1. 내 풀이, 정확성 69.5, 효율성 30.5
public boolean solution_4_1(String s){
    Stack<Character> stack = new Stack<>();

    for(int i=0; i < s.length(); i++){
        if(stack.isEmpty() || s.charAt(i) == '('){
            stack.push(s.charAt(i));
        }
        else if(s.charAt(i) == ')' && stack.peek() == '('){
            stack.pop();
        }
    }
    if(stack.isEmpty()){
        return true;
    }
    return false;
}

1. 스택을 만든다.

2. 넘어온 스트링을 포문을 돌린다.

3. 스택이 비어있거나 스트링의 현재 캐릭터가 ( 면 스택에 넣는다.

4. 그게 아니고 스트링 현재 캐릭터 ) 이고 스택 맨 위 값이 ( 라면 뽑는다.

5. 마지막에 스택이 비어있으면 올바른 것, 아니면 올바르지 않은 것

 

스택 이용 방법(다른 사람 풀이)

public boolean solution_4_2(String s){
    Stack<Character> stack = new Stack<>();

    for(int i=0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == ')'){
            if(stack.isEmpty()){
                return false;
            }
            stack.pop();
        }else {
            stack.push(c);
        }
    }
    if(stack.isEmpty()){
        return true;
    }
    return false;
}

1. 스택을 만든다.

2. 현재 스트링 캐릭터 뽑아놓기

3. 캐릭터 ) 인데 스택이 비어있으면 false 반환

4. 그게 아니라면 그냥 ( 여부 확인하지 않고 뽑아버림

5. 나머지는 모두 값을 넣는다.

6. 비어있지 않으면 올바른 괄호가 아니다.

 

스택으로 풀면 자꾸 효율성이 낮게 나온다.

스택으로 풀지 않는 방법도 있다.

 

스택으로 풀지 않는 방법

public boolean solution_4_3(String s){
    int ans = 0;
    for(int i=0; i < s.length(); i++){
        if(s.charAt(i) == '('){
            ans++;
        }
        else{
            ans--;
        }
        if(s.charAt(i) < 0){
            return false;
        }
    }
    if(ans == 0){
        return true;
    }
    return false;
}

1. 포문을 돌려 현재 스트링 캐릭터가 ( 면 ans++

2. 아니면 --, 만약 마이너스로 한 번 이라도 가면 올바르지 않기 때문에 바로 false 반환

3. 0이면 올바르고 아니면 올바르지 않다.

 

굳이 스택을 만들지 않고도 연산을 통해 해결할 수 있다.