[백준] 좋은 단어(python)

백준, 좋은 단어

3986번: 좋은 단어

TL;DR

• 스택(Stack)

문제 요약

1. A와 B로 이루어진 문자열에 대해서 A와 B끼리 다른 선과 교차되지 않고 선을 그을 수 있는 좋은 문자의 수를 찾아라.

 

- 다른 선과 교차되지 않고 선을 긋는다는 것은 적어도 A와 B가 하나씩 교차되는 형태가 없어야 한다는 뜻이다.

- 스택에 문자를 하나씩 넣어가며 비교하는 방법으로 문제를 해결할 수 있다.

입출력 형태

입출력 예시

 

예시 1 :: ABAB의 경우는 A와 B를 서로 선으로 연결했을 때 두 선이 서로 교차되기 때문에 좋은 단어가 아니다.

예시 2 :: AAA의 경우는 하나의 A가 남게 되므로 좋은 단어가 아니고 AB 역시도 선으로 연결할 수 없는 좋은 단어가 아니다.

풀이

스택을 사용해서 문제를 해결할 수 있다. 스택의 top과 입력받은 문자가 같다면 해당 문자를 스택에서 제거한다.

좋은 단어라면 실행 결과 스택에는 아무 것도 남아 있지 않아야 한다.

import sys
INPUT = sys.stdin.readline

N = int(INPUT())
answer = 0
for _ in range(N):
  stack = []
  for c in INPUT()[:-1]:
    try:
      top = stack.pop()

      if top == c:
        continue
      else:
        stack.append(top)
        stack.append(c)
    except:
      stack.append(c)
  if not stack:
    answer += 1
print(answer)

 

스택의 top과 문자를 비교하며 문제에서 요구하는 것을 구현한 코드이다.

다른 풀이

다른 풀이로는 연속된 문자열이 존재한다는 성질을 사용한 방법이 있겠다. 문자열에 대해서 'AA'와 'BB' 문자열을 공백 문자열로 갱신해가며 문자열이 빌 때까지 확인하면 답을 얻어낼 수 있다.

import sys
INPUT = sys.stdin.readline

N = int(INPUT())
answer = 0
for _ in range(N):
  word = INPUT()[:-1]
  while True:
    word = word.replace('AA', '').replace('BB', '')
    if 'AA' not in word and 'BB' not in word: 
      break
  if word == '':
    answer += 1
print(answer)

 

word에 존재하는 'AA'와 'BB'가 존재하지 않을 때까지 계속해서 공백 문자로 바꿔나간다. 만약 좋은 단어라면 word는 공백문자가 될 것이다. 그럴 경우에는 정답의 개수를 1 늘려준다.