알고리즘 문제 - 0과 1

이동욱

2021/08/28

Categories: 개발

문제 - 0과 1

  • 0과 1로만 이루어진 문자열 S가있다. S는 임의의 위치에서 0과 1이 붙어 있을 경우 두개의 문자열을 짝지어서 제거할 수 있다.

  • 예를 들어서 “1011” 이라는 문자열이 있으면 첫 번째 문자 1과 두번째 문자 0을 짝지어서 제거하면 “11"만 남게 된다.

  • 제거한 후에 연결된 새로운 문자열에서 짝이 생길경우 반복하여 제거할 수 있다.

  • 문자열이 주어질 때 짝지어서 제거하여 만들 수 있는 문자열 중에 가장 짧은 문자열의 길이를 반환하라.

제한 사항

  • 문자열의 길이는 100,000 이하의 자연수이다.
  • 문자열은 0과 1로만 이루어져 있다.

아이디어

  • 스택에 문자열을 순차대로 넣는다.
  • 만약 스택에 문자열이 있으면 하나 꺼내서 앞으로 넣을 문자열이랑 같으면 그냥 넣는다.
  • 아니라면 기존에 있는 문자열을 꺼낸다.

코드

def solution(s: str) -> int:
    s = list(s)
    stack = []
    for ch in s:
        if len(stack) == 0:
            stack.append(ch)
            continue

        if stack[-1] == ch:
            stack.append(ch)
        else:
            stack.pop()


    return len(stack)

참고 문헌

>> Home