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를 초기화시키는 형식으로 작성
- 시간 초과도 안나오고 통과