[프로그래머스] 코딩테스트 연습 - 올바른 괄호 (Java, C)

-링크

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

 

-문제설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

 

 

-제약사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

 

-입출력 예

"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

-해설(Java,C)

스택문제라길래 스택을 써 볼까 했는데, 굳이 스택이 필요 없는 문제였다.

주어진 String을 길이만큼 반복문을 돌리면서, 괄호의 짝을 맞춰주면된다.

왼쪽 괄호 ( 는 +처리하고, 오른쪽 괄호 ) 는 -처리해서 둘의 합이 0이 아니거나, -가 찍히는 순간 괄호의 짝이 맞지 않는 것 이므로, false처리 하면된다. 

if(cnt < 0) break; 조건은 S의 길이가 길고, 맨 처음이나 초반에 오른쪽 괄호 ) 가 많이 나오는 경우 쓸데 없는 연산을 할 필요없이 괄호의 짝이 맞지 않는 걸 알 수 있으므로 빠르게 for문을 나올 수 있도록 넣어 준 조건이다.

결국 for문이 종료되었을 때 cnt가 0이나 0이 아니냐에 따라 true, false로 답을 구할 수 있다.

 

 

-Java 풀이

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int cnt = 0;

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(')
                cnt++;
            else
                cnt--;
            
            if(cnt < 0) break;
        }
        
        answer = cnt != 0 ? false : true;
        
        return answer;
    }
}

 

 

-C 풀이

#include <stdio.h>
#include <stdbool.h>

// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
bool solution(const char* s) {
    bool answer = true;
    int cnt = 0;
    
    for(int i = 0; i < strlen(s); i++){
        if(s[i] == '(')
            cnt++;
        else 
            cnt--;
        
        if(cnt < 0) break;
    }
    
    answer = cnt != 0 ? false : true;
    
    return answer;
}