[백 준/구현] 3986: 좋은 단어

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

3986번: 좋은 단어

핵심 아이디어

이문제를 해결하기 위해 떠올려야하는 것은 바로 stack 자료구조입니다. 이런 문제를 풀때 뭔가 아이디어가 떠오르지 않는다면 ABABABAB처럼 하나를 더 붙여본다든지, 90도 회전 시켜본다든지 등 도식화를 해보는 것이 중요합니다. 

1. 도식화 해보기(똑같은걸 2배로 늘려본다든지, 90도 회전시켜본다든지 등)
2. Stack 자료구조 -> 같은 것끼리 맡물리면 터져 점수를 얻는 게임을 생각해보면 좋을거 같습니다. LIFO, Last In First Out 기반!

풀이

import sys
input = sys.stdin.readline # 빠르게 데이터를 읽어오기 위해 사용
# readline() 함수는 문자 + 개행문자
n = int(input())

count = 0 # 좋은 문자 초기화
for _ in range(n):
	s = input().rstrip()
	stack = []

	for i in s:
		# 만약 스택이 비어있지 않고 새로운 문자와 이전 문자가 같다면
		if stack and stack[-1] == i:
			stack.pop()
		else:
			stack.append(i)
	if not stack: # 만약 스택이 비어있다면
		count += 1
print(count)

 

import sys
input = sys.stdin.readline #readline() 함수는 문자 + 개행문자

 

대량의 데이터를 빠르게 읽을 때 주로 사용됩니다.

for _ in range(n):
	s = input().rstrip()
	stack = []

	for i in s:
		# 만약 스택이 비어있지 않고 새로운 문자와 이전 문자가 같다면
		if stack and stack[-1] == i:
			stack.pop()
		else:
			stack.append(i)
	if not stack: # 만약 스택이 비어있다면
		count += 1

위 로직에서 s = input() 대신 input().rstrip()을 해주는 이유는 sys라이브러리에서 사용하는 readline()이 개행문자(\n)까지 포함해서 읽기 때문에 이를 제거해주기 위해서 rstrip()을 사용하였습니다. 그리고 if stack 은 stack이 비어있지 있는지 확인하는 로직으로 if stack and stack[-1] == s는 스택이 비어있지 않으면서 마지막 문자가 현재 삽입하려고 하는 문자와 같은지 확인하려는 로직입니다.