stack 필수 활용 기술 3

1. 문제

 

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

코딩테스트 연습 - 짝지어 제거하기

 

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.

 

먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다.

 

그 다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다.

 

이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.

 

문자열 s가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성하세요.

 

성공적으로 수행할 수 있으면 1을 아니면 0을 리턴해주면 됩니다.

 

 

2. 제한사항

 

문자열의 길이는 1000000이하의 자연수

 

문자열은 모두 소문자로 이루어져있음

 

 

3. 입출력 예시

 

그림1. 입출력 예시 설명1

 

그림2. 입출력 예시2

 

4. 풀이

 

def solution(s):
    
    len_s = len(s)
    
    stack = []
    
    if len_s % 2 == 1:
        
        return 0
    
    else:
        
        for char in s:
            
            if (len(stack) == 0):
                
                stack.append(char)
                
            elif stack[-1] == char:
                
                stack.pop()
                
            elif stack[-1] != char:
                
                stack.append(char)
                
        if (len(stack) > 0):
        
            return 0
        
        else:
        
            return 1

 

빈 stack을 초기화히고 문자열의 길이를 미리 구해놓는다

 

그리고 먼저 문자열의 길이가 홀수이면 절대로 짝지어서 제거할 수 없으므로 0을 return

 

def solution(s):
    
    len_s = len(s)
    
    stack = []
    
    if len_s % 2 == 1:
        
        return 0

 

다음으로 짝지어서 문자를 제거해야하는데… 도대체 어떻게 하면 가능할까?

 

연속해서 문자를 빼서 두 문자를 비교해서 제거하는 방법

 

stack을 이용해서 할 수 있다

 

else:
        
        for char in s:
            
            if (len(stack) == 0):
                
                stack.append(char)
                
            elif stack[-1] == char:
                
                stack.pop()
                
            elif stack[-1] != char:
                
                stack.append(char)

 

원래 문자열 s에서 문자 하나씩 char을 뺀다

 

stack의 길이가 0이면 s에서 뺀 char을 stack에 집어넣는다

 

stack의 길이가 0이 아니라면 stack에 들어간 마지막 문자 stack[-1]와 s에서 뺀 char을 비교

 

만약 같으면 stack의 원소를 제거함

 

같지않으면 stack에 다시 char을 추가함

 

if (len(stack) > 0):
    
    return 0
        
else:
    
    return 1

 

반복문을 다 돌고 stack의 길이가 0보다 크다는 것은 제거하지 않은 문자들이 들어가 있다는 뜻으로 0을 return하고

 

그렇지 않으면 완벽하게 제거했으므로 1을 return함

 

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

 

예를 들어서 생각해보면 s = ‘baabaa’라고 한다

 

먼저 왼쪽에 b를 빼는데 stack=[]이므로 stack에 b를 집어넣음

 

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

 

stack=[b], s=’aabaa’인데… 이제 s에서 a를 빼

 

그 다음 stack의 길이가 0이 아니므로 stack에 마지막으로 들어간 b와 s의 a를 비교함

 

다르기 때문에 stack에 a를 집어넣어

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

 

stack = [b,a]. s=’abaa’에서 다시 s에서 a를 빼고

 

stack에 마지막에 들어간 a와 s의 a를 비교하면 같으니까 stack의 a를 제거하여

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

 

stack = [b], s=’baa’에서 다시 s에서 b를 빼고

 

stack에 마지막에 들어간 b와 s의 b를 비교해서 같으면 stack의 b를 제거하여

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

 

stack = [], s = ‘aa’에서…. 다시 s에서 a를 빼고..

 

stack=[]니까 그냥 a를 집어넣어서 stack = [a]

 

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

 

stack = [a], s=’a’니까… 다시 stack의 a와 s의 a를 비교해서 같으니까 stack에서 제거…

 

stack에 남은게 없으니까 완벽하게 제거 가능해서 1을 return

 

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

 

이번엔 s=’cdcd’라고 한다면…

 

• stack=[] , s=’cdcd’
• stack = [c], s=’dcd’
• stack = [c,d], s=’cd’
• stack = [c,d,c], s = ‘d’
• stack = [c,d,c,d], s=’’
• stack에 문자가 들어가있어서 제거를 못하는거니까 0을 return

 

 

5. 되돌아보기

 

몇시간동안 했냐.. 6시간 도전했나…

 

stack이라…

 

효율적으로 짠다는게 진짜 얼마나 어렵다는걸 다시한번 느낀다..

 

len()함수나 replace함수… 이런게 문자열이 길어지면 그만큼 검색하는데 시간이 소요되니까 남발하면 시간이 많이 들어서 시간초과로 컷당해

 

이제는 이런걸 나름대로 생각할 수 있다는게 성장했다는거지

 

stack 활용해서 하나의 문자열 내에 연속되는 두 문자를 비교하는 방법을 잘 기억해놓자..

 

이건 경험상 잘 쓰임

 

stack을 어떤 식으로 활용했는지 매번 읽으면서 느낌을 잘 기억