[9012] 괄호

🔗 문제 링크

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

❔ 문제 설명

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

⚠️ 제한사항

• 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.

• 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다.

• 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

---

💡 풀이 (언어 : Java)

올바른 괄호 형태 판별 문제는 몇번 풀어봤다. 내가 생각한 알고리즘은 여는 괄호는 +1, 닫는 괄호는 -1로 합을 카운트해서 중간에 음수가 되면 탈락, 모든 괄호 조회후에는 수가 0이 아니면 여는 괄호와 닫는 괄호의 짝의 수가 맞지 않으므로 탈락이다.

public class Main {
    private static String parentheses(String input) {
        int check = 0;
        for (char pt : input.toCharArray()) {
            // 여는 괄호면 +1, 닫는 괄호면 -1
            check += (pt == '(') ? 1 : -1;
            // 음수로 한번이라도 내려가면 올바른 괄호아님
            if (check < 0) {
                return "NO";
            }
        }
        // 0이면 여는 괄호와 닫는 괄호의 개수가 일치함
        String result = (check == 0) ? "YES" : "NO";
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            System.out.println(parentheses(br.readLine()));
        }
    }
}