[Python] BOJ 3986 : 좋은 단어

https://studyiwthme.tistory.com/176  <- 균형 잡힌 세상이랑 상당히 유사하다.

https://www.acmicpc.net/problem/3986 <- 문제를 풀기 위해선 여기를 보면 된다. 

 

생각해보기

• 좋은 단어란? 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝을 지을 수 있다면..
  • 무슨 말이야
  • 아치형 곡선? 포물선?
• 단어의 수 -> 사용자로부터 받은 입력의 개수 즉, 라인의 개수 
• gpt한테 요구사항 분석 -> 서로 인접한 같은 문자가 있으면, 그 두문자를 제거. 
• 위 과정을 반복하여 모든 문자가 제거될 수 있으면 좋은 단어

요구사항

• 시간 제한 1초 O(n*m) 정도이고  N은 100이하 M은 100,000 충분충분.. 
• 메모리 제한 256MB 넉넉하시다. 
• 서로 인접한 같은 문자가 있으면 그 두 문자를 제거한 후 모든 문자가 제거된 문자열의 개수를 출력해라.

설계 1 

• 사실 균형 잡힌 세상과 상당히 유사하다. 만약 안 풀어봤으면 풀고 풀든 풀고 오든 하면 연습이 됐다.
• 아래는 사용자 정의 함수입니다.
  • 스택을 사용한다.
  • for문에 문자열을 돌린다.
    • stack이 비어 있으면 문자열을 넣는다. 
    • 그렇지 않으면 스택의 상단과 비교해서 같은 문자이면 stack을 pop 한다. 
  • 스택이 남아 있을 경우 return 0 그렇지 않을 시 return 1 을 한다.
• main은 
  • 입력 받은 N만큼 for문을 돌린다. 
    • line = input() 문자열을 입력 받고 
    • result += 사용자정의함수(line) 
  • 결과값을 출력한다. 

구현 1

import sys
input = lambda: sys.stdin.readline().rstrip()

def is_good(s):
    stack = []

    for char in s:
        if not stack:
            stack.append(char)
        elif char =='A':
            if stack[-1] == 'A':
                stack.pop()
                
        elif char == 'B':
            if stack[-1] == 'B':
                stack.pop()
                
    if stack:
        return 0
    else:
        return 1

N = int(input())
result = 0

for _ in range(N):
    line = input()

    result += is_good(line)

print(result)

• 위 경우 백준에서 실패했다고 나온다. 
• 테스트 케이스를 여러 개 해보았는 데 잘 되는 거 같은 데... 안된다
• 처음에 gpt 한테 물어보니깐 맞다고 하더니
• 틀렸습니다 나온다고 했더니 고쳐 주었는 데 아직 나도 잘 모르겠다. 혹시 아시는 분 있으면 댓글 부탁드립니다.

구현 2

import sys
input = lambda: sys.stdin.readline().rstrip()

def is_good(s):
    stack = []

    for char in s:
        if stack and stack[-1] == char:
            # 스택의 최상단과 같은 문자가 있으면 pop
            stack.pop()
        else:
            # 그렇지 않으면 스택에 push
            stack.append(char)

    # 스택이 비어있으면 좋은 단어 (모든 문자가 짝을 이룸)
    return 1 if not stack else 0

N = int(input())  # 입력 문자열의 개수
result = 0

for _ in range(N):
    line = input()
    result += is_good(line)

print(result)