stack 활용법 - 올바른 괄호 문자열 판별

알고리즘/알고리즘 일반

stack 활용법 - 올바른 괄호 문자열 판별

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/76502

코딩테스트 연습 - 괄호 회전하기

programmers.co.kr

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.

만약 A가 올바른 괄호 문자열이라면, (A), [A], {A}도 올바른 괄호 문자열입니다. 예를 들어, []가 올바른 괄호 문자열이므로, ([])도 올바른 괄호 문자열입니다.

만약 A,B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열입니다. 예를 들어, {}와 ([])가 올바른 괄호 문자열이므로, {}([])가 올바른 괄호 문자열이므로, {}([])도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x(0이상 s의 길이 미만)칸만큼 회전시킬때, s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return하세요

2. 제한사항

s의 길이는 1 이상 1000 이하

3. 입출력 예시

4. 입출력 설명

5. 나의 풀이

def solution(s):
    
    answer = 0
    
    from collections import deque
    
    pair_dict = {']':'[', '}':'{', ')':'('}
    
    def inspection(s):
        
        if len(s) % 2 == 1:
            
            return False
        
        else:
            
            if s[0] == ']' or s[0] == ')' or s[0] == '}':
                
                return False
            
            else:
            
                deque_list = deque([])

                deque_s = deque(s)

                while 1:
                    
                    if deque_s == deque():
                        
                        break

                    char = deque_s.popleft()

                    if char == '[' or char == '{' or char == '(':

                        deque_list.append(char)

                    else:
                        
                        if deque_list == deque():
                            
                            return False

                        left_char = deque_list.pop()

                        if pair_dict[char] != left_char:

                            return False

                        else:

                            pass

                return True
    
    length = len(s)
    
    for _ in range(length-1):
        
        ind = inspection(s)
        
        if ind:
            
            answer += 1
        
        deque_s = deque(s)
        
        deque_s.rotate(-1)
        
        s = ''.join(list(deque_s))
    
    return answer

먼저 주어진 문자열이 올바른 괄호 문자열인지 판별하는 알고리즘을 작성해야한다

문자열의 길이가 홀수이면 올바른 괄호 문자열이 아니므로 바로 False를 return

def solution(s):
    
    answer = 0
    
    from collections import deque
    
    pair_dict = {']':'[', '}':'{', ')':'('}
    
    def inspection(s):
        
        if len(s) % 2 == 1:
            
            return False
        
        else:

다음으로 문자열의 첫 문자가 ], ), }이면 올바른 괄호 문자열이 아니니까 바로 False를 return

else:
            
            if s[0] == ']' or s[0] == ')' or s[0] == '}':
                
                return False
            
            else:

이제 모든 조건을 통과하면 올바른 괄호 문자열의 최소 조건을 갖춘거

pop 시간을 줄이기 위해 deque로 만들어서 왼쪽 문자부터 하나씩 차례대로 빼서 char이라고 한다.

char이 [, (, { 이면 stack에 그대로 넣고

else:
            
                deque_list = deque([])

                deque_s = deque(s)

                while 1:
                    
                    if deque_s == deque():
                        
                        break

                    char = deque_s.popleft()

                    if char == '[' or char == '{' or char == '(':

                        deque_list.append(char)

char이 ], ), } 이면 stack에 들어간 문자열과 비교를 함

else:
                        
                        if deque_list == deque():
                            
                            return False

                        left_char = deque_list.pop()

                        if pair_dict[char] != left_char:

                            return False

                        else:

                            pass

                return True

stack이 지금 deque_list이고 문자열은 deque_s인데 여기서 뽑은 문자가 char이란 말이지

char이 ], ), } 여서 stack에 들어간 문자와 비교를 할거임

stack에서 뽑은 문자가 left_char로 [, (, { 중에 하나

앞에서 만든 pair_dict = {']':'[', '}':'{', ')':'('}는 괄호 pair가 맞는지 안맞는지 검사하기 위한거

pair_dict[char]이 left_char과 동일하면 올바른 괄호 문자열의 최소 조건을 갖춘거고

동일하지 않으면 올바른 괄호 문자열이 아니니까 바로 False를 return함

--------------------------------------------------------------------------------------------------------------------------------

예를 들어서 생각을 해보면

" [ ( ( { ) ] "이라고 한다면.... deque_list = [ "[", "(", "(", "{" ] 이 들어가다가... 이제 char을 뽑아보니까 ")"이 나온거임..

그러면 이제 ")"와 deque_list 우측에서 하나 빼서 비교만 해보면 되는거

이 경우 "{"와 ")"여서 올바른 문자열이 아님

" [ ( ( ( ) ] "라고 한다면? deque_list = [ "[", "(", "(", "(" ]까지 들어오다가 char = ")"이 될것인데

deque_list 우측에서 뺀 "("와 char=")"은 pair가 맞으니까

deque_list = ["[", "(", "("]으로 되고 앞에서 한 반복을 다시 하면 된다

그러면 char = "]"이어서 다시 deque_list에서 하나를 뺼건데 left_char = "("이 나오고 char과 pair가 안맞으니까 최종적으로 " [ ( ( ( ) ] "은 올바른 괄호 문자열이 아니게 된다

-----------------------------------------------------------------------------------------------------------------------------------

deque에서 pop을 할때 항상 문제가 언제까지 반복을 해야하느냐?인데

                deque_list = deque([])

                deque_s = deque(s)

                while 1:
                    
                    if deque_s == deque():
                        
                        break

                    char = deque_s.popleft()

                    if char == '[' or char == '{' or char == '(':

                        deque_list.append(char)

                    else:
                        
                        if deque_list == deque():
                            
                            return False

                        left_char = deque_list.pop()

                        if pair_dict[char] != left_char:

                            return False

                        else:

                            pass

                return True

char = } , ) , ] 중에 하나가 나와가지고

left_char과 char을 비교해야하는데 deque_list에서 더 이상 뺄 것이 없다면??? 그러면 그것은 올바른 괄호문자열이 아니다.

예를 들어 s="[]))" 이러면 deque_list = [ "[" ] 에서 char = "]"이 나올때 deque_list의 "["와 pair가 맞아서 deque_list = []으로 빈 리스트 상태에서..

char = ")"이 나올때 deque_list에서 빼서 비교를 해야하는데 deque_list에서 뺄 것이 없으므로 올바른 괄호 문자열이 아니다.

-----------------------------------------------------------------------------------------------------------------------------

deque_s에서 pop을 하다가 deque_s가 빈 리스트가 된다면? 모든 조건을 만족시켰으므로 반복문을 탈출하고 True를 return하면 된다

    length = len(s)
    
    for _ in range(length-1):
        
        ind = inspection(s)
        
        if ind:
            
            answer += 1
        
        deque_s = deque(s)
        
        deque_s.rotate(-1)
        
        s = ''.join(list(deque_s))
    
    return answer

다음 이제 문자열을 왼쪽으로 회전시키면서 올바른 괄호 문자열인지 아닌지 검사하면 된다

길이가 0 이상부터 s의 길이 미만까지니까 length-1번 반복했고

회전을 위해 deque로 만든다음에 rotate(-1)로 왼쪽으로 회전시키고

다시 문자열로 만들어줬다

6. 다른 풀이

가장 좋아요를 많이 받은 풀이를 봐보면

def is_valid(s):

    stack = []
    
    for ch in s:
    
        if not stack:
            stack.append(ch)
            
        elif stack[-1] == '(':
            if ch==')': stack.pop()
            else: stack.append(ch)
            
        elif stack[-1] == '{':
            if ch=='}': stack.pop()
            else: stack.append(ch)
            
        elif stack[-1] == '[':
            if ch==']': stack.pop()
            else: stack.append(ch)

    return False if stack else True

def solution(s):

    answer = 0
    
    for i in range(len(s)):
        answer += is_valid(s[i:]+s[:i])
        
    return answer

올바른 괄호 문자열을 판단하는 알고리즘은 정석대로 stack을 이용해서 비교를 한다

문자열에서 하나씩 문자를 빼서 ch라 두고 stack에 문자가 존재하지 않으면 stack에 집어넣음

근데 이제 (, { , [ , ], }, )이나 상관없이 어떤 문자든 stack에 존재하지 않으면 그냥 집어넣는거

def is_valid(s):
    
    stack = []
    
    for ch in s:
        
        if not stack:
            stack.append(ch)
        
        elif stack[-1] == '(':
            if ch==')': stack.pop()
            else: stack.append(ch)
        
        elif stack[-1] == '{':
            if ch=='}': stack.pop()
            else: stack.append(ch)
        
        elif stack[-1] == '[':
            if ch==']': stack.pop()
            else: stack.append(ch)

    return False if stack else True

근데 이제 stack에 문자가 존재한다면... stack의 우측인 stack[-1]을 봐서

stack[-1]이 ( , { , [ 인 경우에 ch와 비교를 해서 pair가 맞으면 stack의 문자를 빼고 아니라면 stack에 ch를 그대로 넣는거

근데 이제 알고리즘상 stack[-1]이 } , ) , ]일수 있는데 이 경우는 아무것도 안하네?

반복문을 전부 돌았을 때 stack에 아무것도 존재하지 않으면 True를 return하고 stack에 문자열이 존재하면 False를 return함

마지막 return문이 사실은... 아래와 같은 뜻

if stack:
    
    return False

else:
    
    return True

그 다음에 문자열을 회전하면서 검사를 할건데 문자열을 deque없이 회전시키는 방법은

for i in range(len(s)):
    
    string = s[i:]+s[:i]

위와 같이 string을 모두 구해서 문자열을 회전시킬수 있다고함

예를 들어서 s = "[](){}"이면.,..

[](){}
](){}[
(){}[]
){}[](
{}[]()
}[](){

실제로 입출력 예시와 동일하게 나온다

7. 되돌아보기

올바른 괄호 문자열 판별 알고리즘 처음 짤때는 결국 틀렸다.. 힌트를 참조해서 결국에 풀긴했지만

올바른 괄호 문자열을 판별하는 알고리즘은 자주 나오는것 같으니까 잘 기억해두자

deque로 푼 것이 시간에서는 빠르다.. pop속도 차이가 나니까

stack에 [ , ( , { 를 하나씩 쌓아두고... 갑자기 string에서 ] , ) , } 이 나온다면 stack의 맨 우측 문자와 비교해서 pair가 맞는지 비교해본다.

pair_dict = {']':'[', '}':'{', ')':'('}를 만들면 깔끔하게 비교할 수 있다는거 기억해두자.

문자열 회전하는 방법은 deque의 rotate도 있지만 깔끔하진 않다.. for문을 이용한 s[i:]+s[:i]을 기억해둔다면?

'알고리즘 > 알고리즘 일반' 카테고리의 다른 글

완전히 탐색해야할때는.. (0)	2021.11.21
반복문을 줄이는 방법 (0)	2021.11.19
합의 차이가 최소가 되는 분할 1편 (0)	2021.11.16
k fold cross validation을 구하는 알고리즘 문제 복기하기 (0)	2021.11.15
명일방주 픽업을 위한 평균 가챠횟수 4편(일반 헤드헌팅) (0)	2021.11.09

TAGS.

통계학 세상

통계학 세상

통계학 세상