[자바] 프로그래머스 - 올바른 괄호 (Lv2, Java)

문제 : Programmers-올바른 괄호

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 구현
  • 보통 스택으로 설명할 것 같이 생겼는데 어차피 스택을 통한 풀이에서 넣을게 한 종류 뿐이라 딱히 필요없다. 규칙성만 잘 찾아서 구현해주면 된다.

 

풀이

  '('를 +1, ')'를 -1이라고 생각해보자.

"()()"은 anwer이 true였고.  0에서 시작해서 1, 0, 1, 0 이 된다.

"(())()"은 true였고, 1, 2, 1, 0, 1, 0이 된다.

")()("은 false였고, -1, 0, -1, 0이다.

"(()("은 false였고, 1, 2, 1, 2 이다.

 

  answer이 true가 되는 조건은 그럼 다음과 같이 정의해볼 수 있다.

1. 연산 중간에 음수가 되어선 안된다. (열 때 +1, 닫을 때 -1을 해주는데 음수가 중간에 나온다면 열지 않고 닫은게 된다)

2. 모든 괄호를 보고난 후 남은 수가 0이어야 한다. (최종적으로 연 것과 닫은게 쌍이 맞아야 한다.)

 

  반대로 다음의 경우 false를 리턴해주면 된다.

1. 연산 중간에 한번이라도 음수가 나온다.

2. 모든 괄호를 보고난 후 남은 수가 0이 아니다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    boolean solution(String s) {
        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c=='(') cnt++;
            else cnt--;
            if (cnt<0) return false;
        }
        return cnt==0;
    }
}