[Python] 백준 4889번_안정적인 문자열

https://www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

• 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어짐
• 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 함
• 안정적인 문자열의 정의
  • 1) 빈 문자열은 안정적
  • 2) S가 안정적이라면, {S}도 안정적인 문자열
  • 3) S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적
• ex) {}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아님
• 문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지

• 입력
  • 입력은 여러 개의 데이터 세트로 이루어져 있음
  • 각 데이터 세트는 한 줄로 이루어져 있음
  • 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어짐
  • 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수
  • 입력의 마지막 줄은 '-'가 한 개 이상 주어짐
• 출력
  • 각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력
• 시간 제한: 1초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

}{
{}{}{}
{{{}
---
    -> 1. 2
       2. 0
       3. 1
"""

 

 

## 의사코드 ##

# 스택 활용
# for s in string:
    # s가 '{'인 경우
    # stack.append(s)
    # s가 '{'인 경우,
    # 1) 스택이 비어있는 경우, 
        # 연산 수 + 1
        # '{'로 바꿔서 스택.append()
    # 2) 스택이 비어있지 않는 경우, 
        # 스택.pop()

# 최소 연산의 수 = ans + stack에 남아있는 원소의 개수 나누기 2

 

 

 

통과한 코드

 

idx = 0 
while True:
    string = input()
    if '-' in string:
        break

    idx += 1 # 인덱스 + 1
    stack = [] 
    ans = 0 # 안정적으로 바꾸는데 필요한 최소 연산의 수 

    for s in string:
        # 현재 문자가 '{'인 경우, stack에 삽입
        if s == '{':
            stack.append(s)
        elif s == '}':
            # stack이 비어있고 현재 문자가 '}'인 경우, 연산 수행 
            if len(stack) == 0:
                ans += 1
                stack.append('{')
            # stack이 비어있지 않고 현재 문자가 '}'인 경우, stack의 마지막 원소 꺼냄
            else:
                stack.pop()

    # 최소 연산의 수 = ans + stack에 남아있는 원소의 개수 나누기 2
    ans += len(stack) // 2

    print(f"{idx}.", ans)

 

 

• 과정 확인

"""
string: }{
s: }
stack: ['{'] 

s: {
stack: ['{', '{'] 

최종 stack: ['{', '{']
len(stack)//2: 1
1. 2
--------------------------------------------------

string: {}{}{}
s: {
stack: ['{'] 

s: }
pop될 문자: {
stack: [] 

s: {
stack: ['{'] 

s: }
pop될 문자: {
stack: [] 

s: {
stack: ['{'] 

s: }
pop될 문자: {
stack: [] 

최종 stack: []
len(stack)//2: 0
2. 0
--------------------------------------------------

string: {{{}
s: {
stack: ['{'] 

s: {
stack: ['{', '{'] 

s: {
stack: ['{', '{', '{'] 

s: }
pop될 문자: {
stack: ['{', '{'] 

최종 stack: ['{', '{']
len(stack)//2: 1
3. 1
--------------------------------------------------
"""

 

 

 

 

 

참고)

 

https://sophuu.tistory.com/65

[백준][python] 4889 안정적인 문자열 - Greedy