[연습문제] 올바른 괄호

[jeeyeonLIM]

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• ()() 또는 (())() 는 올바른 괄호입니다.
• )()( 또는 (()( 는 올바르지 않은 괄호입니다.
• '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

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

  입출력 예

s	answer
()()	true
(())()	true
)()(	false
(()(	false

입출력 예 설명

• 입출력 예 #1,2,3,4
• 문제의 예시와 같습니다.

[jeeyeonLIM]

나의 풀이

Ver1. 야매로 풀어버리기(만점은 아니지만)

• 먼저 맨앞 맨뒤 검사- 무조건 (로 시작, )로 끝나는지 확인
• 통과하면 st 변수 이용해서 (인경우 +1, )인경우 -1 해서 내부 숫자를 세주려고 했다.

• 하지만 불통. 그 이유는 👉 "()))((()" 반례 때문이다. 즉 갯수는 같다고 하더라도 괄호가 잘 못 닫힌 경우다.

  def solution(s):
  answer = True
  
  if s[0] ==")" or s[-1]=="(" :
      return False
  
  st=0
  for i in s:
      if i =="(":
          st+= 1
      elif i == ")":
          st-= 1
  
  if  st != 0:
      return False
  
  return answer 

  

Ver2. Ver1 보완

• Ver1 대안을 찾고자 st값이 -가 되면(즉, 괄호 (가 나오기도 전에 ')'가 나오는 경우는 return해서 끝내기
• 신기하게도 다른 테케를 통과하지 못했다. 일단 효율성에서 -

  def solution(s):
  answer = True
  if s[0] ==")" or s[-1]=="(" :
      return False
  st=0
  for i in s:
      if i =="(":
          st+= 1
      elif i == ")":
          st-= 1
      if  st < 0:
          return False
          break
  return answer 

  

Ver3. 최종본

• answer 값을 뺐다. 마지막 return을 st값이 0인지 확인해주는 구문으로 변경했다.

• 위에 Ver2에서는 return st값이 (-)인 경우만으로 제한 조건을 걸어줬다. 하지만, ( 문자가 하나가 더 많아서 st값이 (+)값이 될때도 잘못된 괄호를 의미하기 때문에 정확히 0값이 되어야만 올바른 괄호라고 할 수 있다.

  def solution(s):
  if s[0] ==")" or s[-1]=="(" :
      return False
  
  st=0
  for i in s:
      if i =="(":
          st+= 1
      elif i == ")":
          st-= 1
      if st <0 :
          return False
          break
  
  return st == 0

느낀점

• 간단한 것 같은데도 이렇게 오래걸리다니 .. ㅎ

[jeeyeonLIM]

다른 사람들 풀이

Ver1. 리스트에 넣고 빼고, append + pop

def solution(s):
    answer = True
    Queue = []
    for i in s: 
        if i == '(': Queue.append('(')
        else: 
            # try로 실행할 코드를 넣고 except에 예외 발생시 실행할 부분 추가.
            try: Queue.pop() 
            except: return False # 즉 Queue가 빈 리스트여서 pop할게 없을 때 False를 return

    if len(Queue) == 0: return True # 괄호가 올바르게 들어있는 경우
    else: return False

• 출처 : https://eda-ai-lab.tistory.com/478

Ver2.

def is_pair(s):
    x = 0
    for w in s:
        if x < 0:
            break
        x = x+1 if w=="(" else x-1 if w==")" else x
    return x==0

• 여기서 x = x+1 if w=="(" else x-1 if w==")" else x와 같은 형태를 처음봤다. 이건 아래와 같은 if문을 간단하게 표현할 수 있는 방법이다.

  if w=="(" :
  x = x+1
  elif w==")" :
  x= x-1 
  else x= x

• 즉 x = x+1 if w=="(" else x-1 if w==")" else x 로 표현되는 것이며, if 값에 따라서 x에 x+1, x-1, x값이 들어갈 수 있다.