프로그래머스 - 올바른 괄호(Level 2)/Wanna Be 컴잘알

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/12909

코딩테스트 연습 - 올바른 괄호 | 프로그래머스

 

-문제-

 

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

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

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

제한사항

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

---

입출력 예

s	answer
()()	true
(())()	true
)()(	false
(()(	false

 

-접근-

1. stack 형식을 vector로 구현하였다.

2. vector의 가장 마지막 인덱스를 가르키는 top이라는 변수를 만들고 '('이 들어올 때, top+=1을 해준다.

3. ')'이 들어오면 vector[top]이 '('이여야 괄호가 맞아 서로 상쇄된다.

4. 상쇄되면 해당 인덱스의 값을 0으로 만들고 top-=1 해준다.

 

-코드-

 

c++

#include <string>
#include <iostream>
#include <vector>
using namespace std;

bool solution(string s)
{
    bool answer = true;
    vector <int> v ;
    v.resize(s.length());
    int top=-1;
   
    for(int i=0; i< s.length();i++){
        if(s[i]=='('){
            top+=1;
            v[top]=s[i];
        }
        else{
            if(top==-1|| v[top]==')'){
                return false;
            }
            else if(v[top]=='('){
                v[top]=0;
                top-=1;
            }
        }
    }
    
    if(top==-1)
        answer=true;
    else
        answer=false;
    

    return answer;
}

 

python3 (추가 업로드)

from collections import deque

def solution(s):
    answer = True
    q = deque()

    for i in s:
        if i=='(':
            q.append(i)
        else:
            if len(q)==0 or q.pop()==')':
                return False

    if len(q)!=0:
        return False
    
    return True