핵심 알고리즘 파악하기

1. 문제

 

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

코딩테스트 연습 - 올바른 괄호

 

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

 

예를 들어 ‘()()’ 또는 ‘(())()’는 올바른 괄호입니다.

 

‘)()(‘ 또는 ‘(()(‘는 올바르지 않은 괄호입니다.

 

‘(‘ 또는 ‘)’로만 이루어진 문자열 s가 주어졌을 때,

 

문자열 s가 올바른 괄호이면 true를 return하고 올바르지 않은 괄호이면 false를 return하는 solution함수를 완성하세요

 

 

2. 제한사항

 

문자열 s의 길이는 100000이하의 자연수

 

문자열 s는 ‘(‘ 또는 ‘)’로만 이루어져 있습니다.

 

 

3. 예시

 

 

4. 나의 풀이

 

짝지어서 매칭해야하니까 문자열의 길이가 짝수여야만 가능하고 홀수면 무조건 불가능하니까 False를 return하도록

 

len_s = len(s)

if len_s % 2 == 1:
    
    return False

 

이제 문자열의 길이가 짝수이면 True가 될 수 있는데

 

짝짓기가 불가능한 경우가 반드시 있는데

 

첫 문자가 )이거나 마지막 문자가 (이면 절대로 짝지을 수 없으므로

 

def solution(s):
    
    len_s = len(s)
    
    if len_s % 2 == 1:
        
        return False
        
    else:
        
        if (s[0] == ')') or (s[-1] == '('):
            
            return False
            
        else:

 

이제 True가 될 가능성이 있는데… 어떻게 해야 짝짓기가 가능할까

 

문자열 s에서 하나씩 뽑을건데 ) 이게 첫문자면 False로 처리하니까 무조건 첫문자는 ( 이거란 말이지

 

짝짓기가 가능할려면 문자열에서 하나씩 돌때

 

( 이게 나오다가 어느 순간부터는 ) 이게 나올거란 말이지.. 그리고 다시 ( 이게 나올거임

 

생각해보면 다시 ( 이게 나오기 전에 ( 의 개수와 ) 의 개수가 동일하면 그 부분은 짝짓기가 무조건 가능하단 뜻이야

 

 

num1 = 0
num2 = 0

for char in s:
    
    if char == '(':
        
        num1 += 1
        
    else:
    
        num2 += 1
        
        if num1 < num2:
        
            return False

 

s에서 하나씩 빼서 ( 이면 num1을 1 증가시키고 다음에 ) 이게 나오면 num2를 증가시킨단 말이지

 

이제 잘 생각을 해보면 (((((( 이게 나오다가 )))))이게 나오고 있는데

 

이럴때는 num1은 변하지 않고 num2만 증가하는데

 

num2가 어느순간부터 num1보다 커지는 경우가 생길 수 있다

 

예를 들어 ((())))(()()))(()이면 ((( 나오다가 ))))... 나오면 num2=4로 num1=3보다 커지니까 짝짓기 불가능

 

아무튼 그러면 절대로 짝짓기가 불가능하므로 바로 false를 return

 

--------------------------------------------------------------------------------------------------------

근데 이제 for문을 다 돌고나서 num1이 num2보다 큰 경우가 생길 수 있단 말이야..

 

num1 > num2 > num1하고 for문 끝나면...

 

예를 들어 ((())(()))이면?

 

((( 나오다가 )) 나오고 (( ))) 나오는데...

 

(((과 ))에서 왼쪽에 ( 하나가 남아서 num1이 여전히 크니까.. False를 return하지는 않아

 

그러다가 (( 이 나오면서 )))이 나오는데...

 

그러면 오른쪽에 )이 하나 남고

 

왼쪽에 ( 남은거랑 짝이 맞아서 얘는 True를 return해야하는데

 

이게 결과적으로 for문 안에서 False를 return하지 않고 num1이 큰 상태로 for문을 다 도는데

 

for문을 다 돌고 나오면 num1과 num2를 비교해서 서로 다르면 false를 return하고 같으면 true를 return한다

 

if num1 != num2:
    
    return False
    
else:

    return True

 

 

5. 다른 풀이

 

num1과 num2를 0으로 만들어야하는거 아니냐 이런 생각도 했었는데

 

def solution(s):
    
    open_cnt = 0
    
    for c in s:
        
        if c == '(':
            
            open_cnt += 1
            
        elif c == ')':
            
            open_cnt -= 1
            
            if open_cnt < 0:
                
                return False
                
    return open_cnt == 0

 

비슷한 아이디어로 ( 이 나오면 open_cnt의 값을 1 증가 시켜나가고

 

그러다가 ) 이 나오면 open_cnt 값을 1 감소시켜나감

 

그러다가 open_cnt가 음수가 되는건 )의 개수가 ( 보다 갑자기 많아지는거니까 바로 false를 return하고

 

for문을 다 돌면 open_cnt가 0인지 아닌지 검사해서

 

open_cnt가 0이라는 것은 ( 의 개수와 )의 개수가 동일한거임…

 

내가 푼 방법이랑 근본적으로 동일한데 좀 더 깔끔한것 같기도하고..?

 

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

 

아이디어는 똑같은데 num을 세는게 아니라 stack으로 바꿔서 한거네

 

( 이 나오면 stack에 추가 시키고

 

) 이 나오면 stack에 넣은 문자를 하나씩 빼는데

 

만약 에러가 나면 (와 )이 짝이 안맞는거니까 바로 false를 return하고

 

for문을 다 돌고나서 stack의 길이가 0이어야 ( 과 )의 짝이 맞는건데 길이가 0이 아니면 (이 더 많은거임

 

이게 조금 더 직관적으로 보이기도 하고??

 

def solution(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

그냥 open_cnt랑 비슷한데?

 

( 면 x의 값을 1 증가시키고 ) 나오면 1을 감소시킴

 

그러다가 x가 음수가 되는 순간 for문을 탈출하고 x==0에 의해 false를 return

 

혹은 for문을 다 돌다가 x==0이면 (과 )의 개수가 동일해서 true를 return

 

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

근데 이렇게 해도 되거든?? 문맥상… 이게 더 맞는데

 

굳이 뒤에 if w==”)’ else x해가지고 헷갈리게 만드네

 

결국에 모든 풀이가  (의 개수와 )의 개수가 동일해야 짝짓기가 가능하다는 핵심아이디어를 서로 다른 옷을 입혀서 푼거네

 

내가 푼게 제일 빠르긴함

 

 

6. 되돌아보기

 

핵심아이디어인 (의 개수와 )의 개수가 동일해야 짝짓기가 가능하다를 잘 파악한게 좋았다

 

시간을 줄이는데 신경을 많이 쓴게 좋았다

 

처음에 길이 구해서 홀수면 바로 false return

 

첫 문자가 ) 이거나 마지막 문자가 ( 이면 바로 false return

 

num1과 num2를 다시 0으로 안만들어도 된다는 사실을 기억하자

 

for char in s:

    if char == '(':
    
       num1 += 1
       
   else:
   
       num2 += 1
       #########################
       if num1 < num2:
           return False
           ####################
           
if num1 != num2:

    return False
    
else:

    return True

 

저 for문 중간에 if문을 어디에 쓰냐가 또 시간을 줄이는데 일조할 수 있는데

 

num1<num2를 검사하는 것을 num2를 셀때만 해도 되는데 굳이

 

for char in s:

    if char == '(':
    
       num1 += 1
       
   else:
   
       num2 += 1
       #########################
   if num1 < num2:
       return False
           ####################
           
if num1 != num2:

    return False
    
else:

    return True

 

else 밖으로 빼버리면 for문 돌때마다 저 문장을 수행해야하니까 그만큼 쓸모없는 시간이 소요됨

 

그리고 다른 풀이에서 stack을 이용해서 ( 과 )을 짝짓는… 기억을 해두면 좋겠지

 

stack으로 비교하는 기술은 자주 쓰인다

 

혹은 하나의 변수 open_cnt만 사용해서 숫자를 세다가 숫자를 뺐다가

 

두가지는 기억해두면 좋을듯?

 

근데 공부효과가 있긴한가보다 확실히.. 예전에는 손도 못댔는데