Posts 올바른 괄호 [Python]
Post
Cancel

올바른 괄호 [Python]

1. 올바른 괄호


URL : https://programmers.co.kr/learn/courses/30/lessons/12909

1.1 문제 설명

  • 괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다. 예를 들어
  • ()() 또는 (())() 는 올바른 괄호입니다.
  • )()( 또는 (()( 는 올바르지 않은 괄호입니다.
  • ’(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.


1.2 제한사항

  • 문자열 s의 길이 : 100,000 이하의 자연수
  • 문자열 s는 ‘(‘ 또는 ‘)’ 로만 이루어져 있습니다.


1.3 Solution

  • ’(‘가 있다면 ‘)’를 지우는 형식으로 작성 - 시간 초과
  • ’()’를 ‘‘로 바꾸는 형식으로 작성 - 시간 초과
  • ’(‘를 list에 넣고, )가 있다면 list를 초기화시키는 형식으로 작성 - 통과


1.3.1 Soltion (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 시간초과
def solution(s):
    s_list = list(s)
    for i in range(len(s_list)//2):
        if s_list[0] == ')':
            return False
        s_list.remove('(')
        if ')' in s_list:
            s_list.pop(s_list.index(')'))
        else :
            return False
    if len(s_list) ==0:
        return True
    else:
        return False
1
2
s = '()()()()()()'
solution(s)
1
True


1
2
s = ')()('
solution(s)
1
False


1
2
s = '(()('
solution(s)
1
False
  • ’(‘가 있다면 ‘)’를 지우는 형식으로 작성
  • 결과는 잘 나오지만 실제로는 시간 초과


1.3.2 Solution (2)

1
2
3
4
5
6
7
8
9
10
# 시간초과
def solution(s):
    while True:
        if '()' in s:
            s = s.replace('()', '')
        else :
            if len(s) == 0:
                return True
            else:
                return False 
1
2
s = '(()('
solution(s)
1
False


1
2
s = ')()('
solution(s)
1
False


1
2
s = '()()()()()()'
solution(s)
1
True
  • ’()’를 ‘‘로 바꾸는 형식으로 작성
  • 마찬가지로 결과는 잘 나오지만 시간 초과


1.3.3 Solution (3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 이걸로 통과
def solution(s):
    ls = []

    for i in range(len(s)):
        if s[i] == '(':
            ls.append(i)
        elif s[i] == ')':
            if len(ls) == 0:
                return False
            ls.pop()
    if len(ls) != 0:
        return False
    return True
1
2
s = '()()()()()()'
solution(s)
1
True


1
2
s = ')()('
solution(s)
1
False


1
2
s = '(()('
solution(s)
1
False
  • ’(‘를 list에 넣고, )가 있다면 list를 초기화시키는 형식으로 작성
  • 시간 초과도 안나오고 통과
This post is licensed under CC BY 4.0 by the author.