[프로그래머스] 짝지어 제거하기 - 12973

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

문제 분석

이 문제는 문자열의 길이를 봐야 한다. 문자열의 길이는 최대 100만으로 이중 반복문 -> 시간복잡도 O(N*2)인 알고리즘으로 접근하면 시간 초과 발생

=> 시간복잡도 O(N)인 알고리즘을 적용해야함

 

 

해결 과정 직접 그려서 제거해보면 i번째 문제 다음 i+1번째, 반대로 생각해보면 i+1번째 문자는 바로 직전 문자랑 비교
-> 최근 문자와 비교 -> 가장 최근 탐색한 데이터를 먼저 비교 => 스택! 

 

문제 요구사항

짝이 맞는 문자 제거 후 다음 문자열 붙이는 연산 => 팝 연산으로 해결 

 

코드

def solution(s):
	stack = [] #스택 초기화
    for c in s:
    	if stack and stack[-1] == c:
        	stack.pop()
        else:
        	stack.append(c)
    retrun int(not stack)

 

1.  for c in s:
     if stack and stack[-1] == c:  

 

 stack[-1]은 stack의 top

 즉, 이 위치에는 최근에 추가한 데이터가 있음

 스택이 빈 경우도 고려해야 하므로 top의 위치의 원소값부터 체크하지 말고 반드시 stack이 비었는지 체크해야함

 

2. stack.pop()

 

 현재 문자 c와 최근 원소의 문자가 같다면 팝

 스택의 맨 위 문자 제거

 

3. stack.append(c)

 

 스택에 원소가 없다면 푸시

 

4. retrun int(not stack)

 

 모든 문자열을 순회했을 때 스택이 비어 있다면 짝지어 제거하기가 완료된 것

 => 스택이 비어 있으면 1, 그렇지 않으면 0을 반환

 

 

문제 링크

프로그래머스

 

---

알고리즘 수업 더더 열심히 들을걸 그랬다..

그냥 파이썬 코테 풀다가 시간복잡도 다시 생각하려니까 복잡하게 느껴진다.

알고리즘 정리 다시 한번 해야겠다.