[백준] 4949번 균형잡힌 세상 (파이썬)

│문제

4949번: 균형잡힌 세상

 

│풀이

stack=[]

sentence=[]

def judge():

    for letter in sentence:

        if letter=="(" or letter==")":

            if letter=="(": stack.append("(")

            else:

                if not stack:

                    return print("no")

                elif stack[len(stack)-1]=="[":

                    return print("no")

                stack.pop(len(stack)-1)

        if letter=="[" or letter=="]":

            if letter=="[": stack.append("[")

            else:

                if not stack:

                    return print("no")

                elif stack[len(stack)-1]=="(":

                    return print("no")

                stack.pop(len(stack)-1)

    if sentence[len(sentence)-1]!='.':return print("no")

    else:

        if stack:return print("no")

    return print("yes")

while True:

    sentence=list(input())

    if sentence[0]=='.' or len(sentence)==1:            #종료조건

        break

    judge()     #판단하는 함수

    stack.clear()

 

│설명

9012번 괄호문제의 심화 버전 느낌의 문제이다.

처음 풀이를 시작했을 때 문제이해를 잘못하여 [] 따로 () 따로 생각하여 2개의 스택구조가 정상적인 문자열 일 때 참으로 판정하려고 하여 아래와 같이 잘못된 코드를 작성했었다.

 

stack_small=[]

stack_big=[]

sentence=[]

def judge():

    for letter in sentence:

        if letter=="[" or letter=="]":

            if letter=="[": stack_small.append("[")

            else:

                if not stack_small:

                    return print("NO")

                stack_small.pop(len(stack_small)-1)

        if letter=="(" or letter==")":

            if letter=="(": stack_big.append("(")

            else:

                if not stack_big:

                    return print("NO")

                stack_big.pop(len(stack_big)-1)

    if sentence[len(sentence)-1]!='.':return print("NO")

    else:

        if stack_big or stack_small:return print("NO")

    return print("YES")

while True:

    sentence=list(input())

    #print(sentence)

    if sentence[0]=='.' or len(sentence)==1:

        break

    judge()

    stack_big.clear()

    stack_small.clear()

 

하지만 문제를 풀다 ([)]와 같은 괄호 구조도 정상적인 문자열이 아니라는 점을 깨달았다.

이 문제점을 해결하기 위해서는 두개의 스택구조가 아닌 하나의 스택구조에서 조건문을 통해 맞는 방법을 찾아야 했다.

그래서 정답 풀이 코드와 같이 풀이를 하게 되었다.

 

왜 따로 함수를 사용하여 풀었는가??

사실 함수를 이용하지않고 for문만 이용하여도 충분하지만,

 

1.이중 for문과 같이 반복문안에 반복문이 있는 경우

조건문으로 반복문을 2번 탈출하고 싶은 경우 반복문 내의 break보다 함수를 사용하여 return 으로 탈출하는 것이 훨씬 효율적이다. 하지만 함수의 호출과 리턴이 반복 될수록 시간 복잡도와 공간복잡도가 증가하는 단점이 있다.

 

2.시간 초과의 문제가 없는경우

시간 복잡도와 공간 복잡도가 증가하지만 제일 큰 장점은 코드를 파악하는데 직관성이 좋아진다.

 

이번 문제의 경우 이중 반복문을 탈출해야하는 경우는 없지만,

 평소 이중 반복문이 나오는 경우 시간 복잡도 중요문제인지 아닌지 파악후 따로 함수로 빼서 작성하는 추세이다.