해당 문제는 프로그래머스 고득점 kit 큐에 속하는 문제로, list안에 있는 값을 비교 후 제거하는 것이 풀이의 핵심이다. 파이썬에서는 deque 패키지를 활용하여 큐 문제를 해결한다.
큐(Queue) 알고리즘에 대한 설명은 이 포스팅 참고 !
문제
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.입출력 예
| s | answer |
|---|---|
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
입출력 예 설명
- 입출력 예 #1,2,3,4
문제의 예시와 같습니다.
문제 링크
내 풀이
from collections import deque
def solution(s):
queue = deque(list(s))
a = queue.popleft()
if a == '(' and len(queue)%2 == 1: # 시작하는 괄호가 (이고 괄호의 총 개수가 짝수일 경우만
count = 1
while queue:
b = queue.popleft()
if a == b : # b가 ( 이면
count += 1
else: # b가 ) 이면
count -= 1
if count < 0:
return False
return True if count == 0 else False
else:
return False
-
이것도 level 2 문제이지만 직전 기능개발 문제에 비해서는 풀만 했다. (25분 소요) 사실 코드를 짜서 test case 4개를 맞추는 것까지는 어렵지 않았지만 반례를 찾는 부분에서 조금 애먹었다.
-
나의 경우, count 라는 변수를 활용해서 짝이 맞으면 count가 0이므로 True를 반환해야한다. 라는 큰 틀을 가지고 문제를 풀이했다.
if count < 0:
return False- 이 부분의 코드를 가장 마지막에 추가했다. 만약 s가
"()) ..."일 경우
처음()<- 이부분은 문제가 없지만 바로 나오는 괄호가)이므로 올바르지 않은 괄호가 된다. 이때 count가 음수가 되기 때문에 count가 음수가 되면 False를 return 하도록 했더니 case 4개 정도의 반례가 해결되었다.
다른 사람의 풀이
def solution(s):
st = list()
for c in s:
if c == '(':
st.append(c)
if c == ')':
try:
st.pop()
except IndexError:
return False
return len(st) == 0-
st라는 빈 리스트를 생성하고 s를 for문을 돌면서
(괄호일 경우 st에 append 해주고,)괄호일 경우 st를 pop 하도록 하였다. 만약 st가 빈 리스트일 경우 try except문으로 처리해주었다 ... <- 이게 굉장히 멋있는 포인트 -
마지막 최종 return 값은 st 리스트의 길이로 처리해주었는데, 이것도 나였으면
if not st:
return True
else:
return False이렇게 엄청 길게 했을텐데 ..........
