책 리뷰/파이썬 알고리즘 인터뷰

9장 스택,큐(2) - 스택이란? (예제-중복문자제거)

조조링 2024. 11. 19. 00:48
728x90
반응형

 

중복된 문자를 제외하고 사전식 순서로 나열하라

입력: "bcabc" / 출력: "abc"
입력: "cbacdcbc" / 출력: "acdb"

 

 

풀이. 스택을 이용한 문자 제거

import collections

def removeDuplicateLetters(s: str) -> str:
    counter, seen, stack = collections.Counter(s), set(), []
    
    for char in s:
        counter[char] -= 1  # 현재 문자의 개수를 하나 줄임
        
        if char in seen:  # 이미 스택에 추가된 문자라면 건너뜀
            continue
        
        # 스택에서 문자를 제거할 조건:
        # 1. 스택이 비어있지 않을 것
        # 2. 현재 문자(char)가 스택의 마지막 문자(stack[-1])보다 사전식으로 앞에 있을 것
        # 3. 스택의 마지막 문자가 뒤에 다시 등장할 수 있을 것 (counter[stack[-1]] > 0)
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            seen.remove(stack.pop())  # 스택에서 제거하고 seen에서도 제거
        
        stack.append(char)  # 현재 문자를 스택에 추가
        seen.add(char)      # seen 집합에도 추가
    
    # 스택에 있는 문자들을 하나로 합쳐 결과 반환
    return ''.join(stack)

 

주요 개념 및 동작 원리

  1. collections.Counter:
    • 문자열의 각 문자가 몇 번 등장하는지 세는 딕셔너리 형태의 객체
    • 매 루프에서 counter[char] -= 1로 현재 문자의 남은 개수를 줄인다.
  2. seen:
    • 이미 스택에 추가된 문자를 추적하는 집합(set)
    • 중복된 문자를 방지하기 위해 사용된다.
  3. stack:
    • 결과 문자열을 저장하는 스택
    • LIFO(Last In, First Out) 구조로 문자를 추가하거나 제거하며, 최적의 결과를 도출한다.
  4. 조건에 따른 스택에서 문자 제거:
    • stack[-1]이 현재 문자보다 사전식으로 뒤에 있고,
    • stack[-1]이 나중에 다시 등장할 수 있는 경우에 스택에서 제거
    • 이를 통해 결과 문자열의 사전식 순서를 유지한다.
  5. return ''.join(stack):
    • 최종적으로 스택에 남은 문자들을 연결하여 결과 문자열을 반환한다.

예제 및 동작 과정

입력: "cbacdcbc"

  1. 초기 상태:
    • counter = {'c': 4, 'b': 2, 'a': 1, 'd': 1}
    • seen = {}
    • stack = []
  2. 첫 번째 문자 c:
    • counter['c'] -= 1 → {'c': 3, 'b': 2, 'a': 1, 'd': 1}
    • c는 seen에 없으므로 추가:
      stack = ['c'], seen = {'c'}
  3. 두 번째 문자 b:
    • counter['b'] -= 1 → {'c': 3, 'b': 1, 'a': 1, 'd': 1}
    • b는 seen에 없으므로 추가:
      • stack = ['c', 'b'], seen = {'c', 'b'}
  4. 세 번째 문자 a:
    • counter['a'] -= 1 → {'c': 3, 'b': 1, 'a': 0, 'd': 1}
    • a는 seen에 없으므로 스택에 추가하려고 함.
    • 스택에서 제거 조건 확인:
      • a < b이고 counter['b'] > 0:
        • stack.pop() → stack = ['c'], seen = {'c'}
      • a < c이고 counter['c'] > 0:
        • stack.pop() → stack = [], seen = {}
    • a 추가:
      • stack = ['a'], seen = {'a'}
  5. 네 번째 문자 c:
    • counter['c'] -= 1 → {'c': 2, 'b': 1, 'a': 0, 'd': 1}
    • c는 seen에 없으므로 추가:
      • stack = ['a', 'c'], seen = {'a', 'c'}
  6. 다섯 번째 문자 d:
    • counter['d'] -= 1 → {'c': 2, 'b': 1, 'a': 0, 'd': 0}
    • d는 seen에 없으므로 추가:
      • stack = ['a', 'c', 'd'], seen = {'a', 'c', 'd'}
  7. 여섯 번째 문자 c:
    • counter['c'] -= 1 → {'c': 1, 'b': 1, 'a': 0, 'd': 0}
    • c는 이미 seen에 있으므로 건너뜀.
  8. 일곱 번째 문자 b:
    • counter['b'] -= 1 → {'c': 1, 'b': 0, 'a': 0, 'd': 0}
    • b는 seen에 없으므로 추가:
      • stack = ['a', 'c', 'd', 'b'], seen = {'a', 'c', 'd', 'b'}
  9. 여덟 번째 문자 c:
    • counter['c'] -= 1 → {'c': 0, 'b': 0, 'a': 0, 'd': 0}
    • c는 이미 seen에 있으므로 건너뜀.

최종 결과

스택: ['a', 'c', 'd', 'b']
결과 문자열: 'acdb'

 

시간 및 공간 복잡도

  1. 시간 복잡도:
    • 문자열의 길이를 n이라 할 때, 각 문자를 한 번씩 순회하므로 O(n)
    • 스택의 연산(push, pop)은 상수 시간에 이루어진다.
  2. 공간 복잡도:
    • Counter, seen, stack은 입력 문자열에 비례하므로 O(n)
728x90
반응형