출처
: Programmers
문제
괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- ”()()” 또는 “(())()” 는 올바른 괄호입니다.
- ”)()(“ 또는 “(()(“ 는 올바르지 않은 괄호입니다. ‘(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
(생략)
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def solution(s):
'''
- 맨 처음이 ')'이면 바로 False
- 왼쪽cnt보다 오른쪽 cnt가 커지면
False
'''
# 스택
# stack = []
# 스택의 포인터
pointer_stack = 0
# 왼쪽 괄호
left_cnt = 0
# 오른쪽 괄호
right_cnt = 0
size_s = len(s)
is_right = True
for i in range(size_s):
temp = s[i]
if (pointer_stack == 0 and temp == ")"):
is_right = False
break
else:
# stack.append(temp)
pointer_stack += 1
if (temp == "("):
left_cnt += 1
elif (temp == ")"):
right_cnt += 1
if (right_cnt > left_cnt):
is_right = False
break
if (left_cnt != right_cnt):
is_right = False
answer = is_right
return answer
어쩌면 스택Stack이라는 개념의 풀이는
스택이라는 특정 형태의 리스트가 중요한 게 아닐지도 모르겠다.
이 문제에선
리스트를 만들어서 스택 형태로 넣지 않아도 무방했다.
하지만,
left_cnt와 right_cnt, pointer_stack은
최소한 나의 풀이에선 필수적이었다.
다른 사람들의 풀이
1
2
3
4
5
6
def is_pair(s):
pair = 0
for x in s:
if pair < 0: break
pair = pair + 1 if x == "(" else pair - 1 if x == ")" else pair
return pair == 0
(출처: 프로그래머스 스쿨 다른사람 풀이)
너무 깔끔하다…
외형적으로는 스택이 쓰이진 않았지만
결국 이런 형태도 큰 의미에선 스택이 아닌가 싶기도 한다.