17609 회문
-
백준 17609 회문Algorithm/BOJ 2021. 5. 3. 11:07
출처: www.acmicpc.net/problem/17609 분류: 투포인터 접근방식 하나를 제거해서 펠린드롬이 될 수 있는 유사 펠린드롬인지까지 확인해야 하는 문제였습니다. 처음에 반례를 생각 못하고 잘못 접근해서 틀렸었는데요, 양쪽 끝(s, e)에서부터 확인하다가 문자가 다를 때, s+1 문자와 e 문자가 같은지, 아니라면 s문자와 e-1 문자가 같은지 확인하고 둘다 아니라면 2를 출력하게 했었는데요, 여기의 반례는 baaba 가 됩니다. s = 0, e = 4 에서 다를 때 s+1와 e 번째 문자는 둘다 a 로 같은데 이때는 유사회문도 될 수 없습니다. 하지만 맨 뒤의 문자 a를 지워서 s == e-1 로 확인하면 유사회문이 되는 걸 확인할 수 있습니다. 따라서 (s+1, e) 와 (s, e-1) ..