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

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

4949번: 균형잡힌 세상

---

나의 풀이

기존의 괄호 '(', ')'만 탐색하는 과정에서 썼는데 시간이 오래 걸렸던 방법을 사용했다.

괄호 1개만 확인한다면 '(' 일 때 +1, ')' 일 때 -1로 푸는 게 더 빠름

 

이 문제는 괄호 '()' '[]'가 제대로 있는지 그리고 서로 겹쳐있지 않는지 확인해야 함

([)] 이 경우에는 no를 출력해야 함

풀이는 위와 같이 ')'와 ']'가 나왔을 때 짝이 맞다면 짝을 없애고 짝이 아니라면 no를 출력함

import sys

while True:
    s = list(sys.stdin.readline())[:-1]
    answer = []
    if s == ['.']:
        break

    while s:
        pare = s.pop()
        if pare == ')' or pare == ']':
            answer.append(pare)

        elif pare == '(':
            if answer and answer[-1] == ')':
                answer.pop()
            else:
                answer.append(pare)
                break
        elif pare == '[':
            if answer and answer[-1] == ']':
                answer.pop()
            else:
                answer.append(pare)
                break
    if answer == []:
        print('yes')
    else:
        print('no')

---

다른 사람의 풀이

while이 아니라 for문을 쓰면 더 빠르게 풀 수 있음

import sys
input = sys.stdin.readline

while True:
    str = input().rstrip()
    q = []

    if str == ".":
        break

    for i in str:
        if i == '(' or i == '[':
            q.append(i)
        elif i == ')':
            if len(q) > 0 and q[-1] == '(':
                q.pop()
            else:
                q = ['no']
                break
        elif i == ']':
            if len(q) > 0 and q[-1] == '[':
                q.pop()
            else:
                q = ['no']
                break
    if len(q) == 0:
        print('yes')
    else:
        print('no')

---

Trials and Errors

 

1) if answer and answer [-1] == ')'

2) if answer[-1] and answer == ')'

두 코드의 차이점

1)은 answer가 True이면 answer[-1] == ')'을 검사함

2)은 answer[-1] == ')'가 True이면 answer을 검사함

 

2) 코드를 쓰면 answer에 아무것도 안 들어있을 때 오류를 발생시키지만 1)은 answer에 아무것도 안 들어있어도 오류가 발생하지 않음

---

len(answer)과 answer==[]의 시간 복잡도

answer(list)의 길이가 짧다면 상관없지만 answer의 길이가 길어질수록 len()은 조심히 써야 함

 

len이 변하지 않는다면 for문에 len 변수를 따로 선언시켜 쓰는 것이 좋음

 

import time

a = [i for i in range(1000000000)]


start = time.time()

if len(a) == 0:
    print('no')
else:
    print('yes')

end = time.time()
print(f"{end - start:.50f} sec")


start = time.time()

if a == []:
    print('no')
else:
    print('yes')

end = time.time()
print(f"{end - start:.50f} sec")