스택문제 괄호

입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]

[문제 5번] 고장난 프린터

작성

470

강사님 안녕하세요!! 이번에 기업 코딩테스트를 보게 되었는데 예상치 못한 문제가 나와 매우 당황했었습니다....

제가 평소에 풀던 괄호 문제는 대괄호, 중괄호, 소괄호 순서 상관없이 제대로 여는 괄호, 닫는 괄호가 정확하게 되어있다면 문제를 풀 수 있었던 유형이었습니다. ex) { ( [ [ ] ] ) } <-이건 스택으로 풀면 len(stack)==0 이 나와 answer=YES 가 되는 식의 문제였는데....

이번 코딩테스트에서는 세상에... 여는 괄호, 닫는 괄호가 정확히 되어있는 조건에 + 무조건 대괄호 , 중괄호, 소괄호 이 순서를 유지해야한다는 조건이 있었습니다. 한마디로

ex) { ( [ [ ] ] ) } <- 이건 중괄호가 제일 바깥에 있고 소괄호 안에 대괄호가 있으니 성립하지 않고

[ [ { { ( ) } } ] ] <- 이런 식으로 괄호가 유지되어야만 성립이 되는 문제라고 하더군요..... 결국 코딩테스트 탈락의 고배를 마시게 되었는데... 저 상황이라면 어떤식으로 접근을 해야하는 걸까요? 지원자들의 후기를 들어보니 해쉬 셋으로 풀면 된다고 했지만 그 코드를 어떻게 작성해야할지 몰라 매우 난감한 상황입니다..

python 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

문제의 세부사항을 정확하게 몰라서 위에 글만 가지고 해보자면 아래와 같이 하면 되지 않을까 생각합니다.

def solution(s):
    dic = {')' : '(', ']' : '[', '}': '{'}
    flag = {'[' : False, '{' : False, '(' : False}
    stack = []
    for char in s:
        if char in '({[':
            stack.append(char)
            flag[char] = True
            if char == '[':
                if flag['{'] == True or flag['('] == True:
                    return False
            elif char == '{':
                if flag['('] == True:
                    return False     
        else:
            if stack:
                top = stack.pop()
                if (dic[char] != top):
                    return False
            else:
                return False
    if stack:
        return False
    return True


print(solution("[[{{()}}]]"))
print(solution("{([[]])}"))
print(solution("[{}{{}}()"))
print(solution("[]{}()"))
print(solution("{{()()}}"))

jocharlie

질문자

와........................정확합니다 이 풀이가 맞네요.......... 정말 ....와 갓태원선생님..... 너무 감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

인프런 AI 인턴

안녕하세요 jocharlie 님, 인프런 AI 인턴이에요. 코딩테스트에서 괄호 문제에 대하여 질문하신 것 같아요.

주어진 문제에서는 괄호가 정확히 되어 있을 뿐만 아니라, 대괄호, 중괄호, 소괄호의 순서도 유지되어야 한다는 조건이 있습니다. 이런 문제는 스택(Stack) 자료구조를 활용하여 해결할 수 있습니다.

스택은 Last-In-First-Out (후입선출) 구조로 동작하는 자료구조입니다. 괄호 문제를 스택으로 해결하려면 다음과 같은 접근법을 사용할 수 있습니다.

주어진 문자열을 순회하면서 여는 괄호일 경우 스택에 추가합니다.
닫는 괄호일 경우 스택의 맨 위에 있는 괄호와 짝을 이루는지 확인합니다.
- 짝을 이루는 괄호일 경우, 스택에서 맨 위의 괄호를 제거합니다.
- 짝을 이루지 않는 괄호일 경우, 문제 조건에 맞지 않으므로 종료합니다.
문자열 순회가 끝나고 스택이 비어있는 경우, 모든 괄호가 정확하게 짝을 이루는 것이므로 조건을 만족합니다. 그렇지 않으면 조건을 만족하지 않습니다.

위의 접근법을 구현하기 위해 해시셋(Hashset)을 사용할 수도 있습니다. 스택을 사용하지 않고도 괄호의 짝을 매칭할 수 있습니다. 해시셋에는 여는 괄호와 닫는 괄호의 짝이 저장되어 있어야 합니다. 여는 괄호가 나타날 때마다 해시셋에 추가하고, 닫는 괄호가 나타날 때마다 해시셋에서 짝을 확인하는 방법입니다.

이런 방식으로 스택을 이용하거나 해시셋을 활용하여 괄호 문제에 접근하면 됩니다. 문제에 따라 가장 적합한 방법을 선택하여 구현하시면 됩니다. 좋은 결과를 얻으실 수 있기를 바랍니다. 테스트에서 화이팅하세요!

인프런 커뮤니티 질문&답변

스택문제 괄호