BOJ 17609 회문

태그

문자열

두 포인터

생성일

2024/12/11 12:11

URL

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

문제 설명

•

TTT개의 문자열에 대해, 각각의 문자열이 회문인지, 유사회문인지를 판단하는 문제

◦

유사회문이란 한 문자를 삭제하여 회문이 되는 문자열을 의미한다.

예제 입력/출력

•

입력1

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc
Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

1≤T≤301 ≤ T ≤ 301≤T≤30

•

3≤N3 ≤ N3≤N(각 문자열의 길이) ≤100,000≤ 100,000≤100,000

문제 풀이

•

접근1 길이가 NNN인 문자열이 회문인지를 판단하는 방법

◦

브루트 포스적으로 확인하는 방법 - O(N)O(N)O(N)

•

접근2 길이가 NNN인 문자열이 유사회문인지를 판단하는 방법

◦

모든 문자에 대해 지워본 후에, 각각에 대해 회문인지를 판단하는 방법 - O(N2)O(N^2)O(N2)

◦

브루트 포스적인 풀이에서 조금 더 효율적인 풀이를 생각 (= 그리디한 사고 과정)

▪

문자열 양 끝에서부터 포인터를 두고 확인하다가 문자가 다를 경우, 그 중 한 문자를 제거했을 때 나머지 문자열이 회문인지를 확인한다. - O(N)O(N)O(N)

풀이 코드

•

투 포인터 - O(T⋅N)O(T \cdot N)O(T⋅N)

def is_palindrom(s):
	for left in range(len(s)):
		right = len(s) - left - 1
		if s[left] != s[right]:
			return False
	return True

def is_pseudo_palindrome(s):
	for left in range(len(s)):
		right = len(s) - left - 1
		if s[left] != s[right]:
			s1 = s[:left] + s[left + 1:]
			s2 = s[:right] + s[right + 1:]
			if is_palindrom(s1) or is_palindrom(s2):
				return True
			else:
				return False

def solve():
	# input
	S = input()

	# solve
	if is_palindrom(S):
		print(0)
		return

	if is_pseudo_palindrome(S):
		print(1)
		return

	print(2)


T = int(input())
for _ in range(T):
	solve()
Python
복사