[python] 4889, 안정적인 문자열 : 그리디, 문자열, 스택, 자료구조

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

4889번: 안정적인 문자열

 

[문제]

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

 

[입력]

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

 

[출력]

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

 

[예제]

 

[풀이]

💡 문제 요약 : 모든 문자열에서 "{}"가 성립하도록 하는 최소 연산의 수

💡 풀이 포인트

 stack을 이용하면 풀리는 문제였다 !! "{{}}" 또한 안정적인 문자열로 보고 있기 때문에 무작정 다음 문자와 비교해서는 답을 얻을 수 없고 스택에 '{'가 있을 때, '}'가 들어오면 성립 > 성립 > 성립을 반복해서 풀어야 하는 문제였다.

 

cnt = 0
while True:
  cnt += 1
  sen = input()
  if '-' in sen: break
  
  stack = sen[0]
  for i in sen[1:]:
    if stack and stack[-1] + i == '{}':
      stack = stack[:-1]
    else:
      stack += i
  
  answer = 0
  for i in range(0, len(stack), 2):
    if stack[i] != stack[i + 1]:
      answer += 2
    else:
      answer += 1
  
  print(f'{cnt}. {answer}')

나의 풀이는

1 ) 스택에 가장 첫번째 문자 추가

2 ) 첫번째 반복문

     ( 1 ) 스택에 있는 가장 마지막 문자와 현재 반복문의 문자가 '{}'를 이루면 스택의 가장 마지막 문자를 삭제

     ( 2 ) 스택에 있는 가장 마지막 문자와 현재 반복문의 문자가 '{}'를 이루지 않으면 스택에 추가

3 ) 두번째 반복문

문자는 반드시 짝수개로만 주어지기 때문에 스택의 앞부터 문자를 두개씩 묶어나가며 연산을 수행하고 수행 횟수를 더해주면 됨. 경우의 수는 두 가지로, '{{'이거나 '}{'인 경우만 존재함.

     ( 1 ) 만약 문자가 같다면 = '{{'이라면 OR '}}'이라면 → 앞뒤 중 하나의 문자만 바꿔주면 됨 → 연산 1회 수행

     ( 2 ) 만약 문자가 다르다면 = '}{'이라면 → 앞뒤 모두 바꿔주어야 함 → 연산 2회 수행

였는데 ...

 

더 간단한 풀이가 있었다 !

메모리 차이는 없었고 시간 차이가 한 8 ms정도 있었다. 그리고 풀이를 찾아봤을 때 대부분의 사람들이 이렇게 풀었어서 이 방식도 기억해두면 좋을 것 같아서 기록해두려 한다 ㅎㅎㅎ

개인적으로 나의 풀이보다 좋다고 느꼈던 이유는 반복문이 한 번만 실행되고 훨씬 효율적이라고 느껴졌다.

 

cnt = 0
while True:
  cnt += 1
  sen = input()
  if '-' in sen: break

  answer = 0
  stack = []
  for i in sen:
    if i == '{':
      stack.append(i)
    else:
      if stack:
        stack.pop()
      else:
        answer += 1
        stack.append('{')

  answer += len(stack) // 2
  print(f'{cnt}. {answer}')

 

이 풀이의 포인트는 스택에 '{' 문자만 추가한다는 점이다 !!

1) 반복문 실행

     ( 1 ) 문자가 '{'이면 무조건 스택에 push

     ( 2 ) 문자가 '}'이고 스택에 문자가 있으면(= '{'가 앞에 존재했으면) 스택을 pop

     ( 3 ) 문자가 '}'이고 스택에 문자가 없으면(= '}'와 매칭되는 '{'가 앞에 없었으면)

             & '{'로 변환해 스택에 push  → 연산 1회 수행

            → 위에서 말했듯이, 같은 문자가 두번 연속 나오면 연산 1회 & 다른 문자 '}{'가 나오면 연산 2회이기 때문에

                 '{'로 변환해 스택에 push해주면 연산 횟수가 성립한다.

2) answer + len(stack) // 2 : '{{'가 스택에 존재한다면 변환시키는 연산 횟수를 answer에 추가