백준_python 4949번 균형잡힌 세상(출력 초과)

<문제 링크>

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

 

<정답 코드>

sol1)  stack 배열에 열린 괄호는 추가, 닫힌 괄호는 열린 괄호 있으면 pop으로 제거

 

while True:
    stack = []
   
    line = input()
    
    if line == '.':                    # 종료조건
        break    
    
    for i in line:
        if i == '(' or i == '[':    # 열린 괄호면 stack에 추가
            stack.append(i)
        elif i == ')':                # 닫힌 괄호면 열린괄호 존재 유무에 따라 처리
            if len(stack) > 0 and stack[-1] == '(':
                    stack.pop()
            else:
                stack.append(i)
                break
        elif i == ']':                # 닫힌 괄호면 열린괄호 존재 유무에 따라 처리
            if len(stack) > 0 and stack[-1] == '[':
                stack.pop()
            else:
                stack.append(i) 
                break
    
    if len(stack) == 0:                # 모든 괄호 쌍이 맞아 stack이 비어있으면 yes
        print('yes')
    else:
        print('no')                    # 모든 괄호 쌍이 맞지 않아 stack이 비어있지 않으면 no

 

 

 

sol2)   열린괄호와 닫힌괄호 갯수 세서 판단 후, 괄호 문자만으로 된 배열 만들어 괄호쌍 찾아 제거

 

import sys
 
input = sys.stdin.readline
 
while True:
    line = input().rstrip()
 
    if line == '.':
        break
 
    # 열린 괄호와 닫힌 괄호 숫자 일치하지 않으면 no 출력
    if line.count('(') != line.count(')') or line.count('[') != line.count(']'):
        print('no')
        continue
    
    # 괄호 문자만 포함하는 문자열 b 생성
    b = ''
 
    for i in line:
        if i in '()[]':     # line의 요소 i가 괄호면 b에 추가
            b += i
    
    # 연속된 괄호쌍 () 또는 [] 찾아 replace로 제거
    while '()' in b or '[]' in b:
        if '()' in b:
            b = b.replace('()', '')
        if '[]' in b:
            b = b.replace('[]', '')
    
    if b == '':
        print('yes')
    else:
        print('no')

 

 

---

출력 초과

입력을 input()이 아니라 sys.stdin.readline()으로 받을 경우 출력 초과 오류 발생

sys.stdin.readline()으로 입력받은 문자열은 개행 문자('\n')를 포함하고 있어

마침표로 실행되는 종료 조건( if line == '.' ) 제대로 수행되지 않음

readline()을 사용할 경우 rstrip()을 통해 문자열 뒤 공백(개행문자 포함)을 제거해야 입력값이 마침표인지 정확히 판별 가능

 

 

sol 1 vs sol 2

sol 2의 replace 연산은 내부적으로 새로운 문자열을 생성하기 때문에

 => 매우 긴 입력 문자열의 경우, sol 1이 성능상 유리할 수 있음

 

그러나 문제에서 입력 문자열은 최대 100글자로 명시되어 있으므로

=> 채점 결과 sol 2가 sol 1보다 약 5배 빠른 연산속도 보임

 

문제 상황과 데이터 형태에 따라 적합한 방식 사용해야함