[BOJ/Java] 17609. 회문

[BOJ/Java] 17609. 회문

17609번: 회문

---

문제 해석

문제 "회문"은 문자열이 회문인지, 유사 회문인지, 일반 문자열인지를 판별하는 문제다. 회문은 정방향과 역방향이 같은 문자열을 말하고, 유사 회문은 한 문자를 제거하여 회문이 될 수 있는 문자열을 의미한다. 이 문제를 해결하기 위해서는 각 문자열에 대해 투 포인터 알고리즘을 활용하여 양 끝에서부터 문자를 비교하면서 회문 여부를 확인해야 한다.

풀이 과정

이 코드는 투 포인터를 활용하여 문자열의 시작 인덱스와 끝 인덱스를 가리키는 start와 end를 사용한다. 다음과 같은 조건으로 문자열을 확인한다:

 

1. 회문 확인: start 위치의 문자와 end 위치의 문자가 같다면 두 인덱스를 각각 내부로 이동시켜 계속 비교한다.
2. 유사 회문 확인: start 위치의 문자와 end 위치의 문자가 다를 경우, 두 가지 경우를 확인한다.
   • start 인덱스만 하나 증가시켜 다시 회문 검사를 시도한다.
   • end 인덱스만 하나 감소시켜 다시 회문 검사를 시도한다. 이 두 경우 중 최소 값을 취하여 유사 회문 여부를 확인한다.

 

종료 조건은 다음과 같다:

 

• 제거해야 하는 문자의 수가 2개 이상이면 해당 문자열은 일반 문자열이다 (return 2).
• start가 end보다 같거나 크면 탐색을 종료하고 cnt 값을 반환한다.

 

이런 방식으로 각 문자열에 대해 회문, 유사 회문, 일반 문자열을 판별할 수 있다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No17609;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	private static int N;  // 테스트 케이스의 수
	private static String string;  // 검사할 문자열
	private static char[] stringArray;  // 문자열을 배열 형태로 변환하여 사용
	private static int length;  // 문자열의 길이

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());  // 테스트 케이스 수 읽기
		
		for (int i = 0; i < N; i++) {
			string = br.readLine();  // 문자열 읽기
			length = string.length();  // 문자열 길이 저장
			stringArray = new char[length];  // 문자열을 배열로 변환
			stringArray = string.toCharArray();  // 문자열을 char 배열로 변환
			sb.append(find(0, length-1, 0)).append("\n");  // 회문 판별 함수 호출 및 결과 추가
		}
		
		bw.write(sb.toString());  // 결과 출력
		bw.flush();
		bw.close();
	}
	
	private static int find(int start, int end, int cnt) {  // 회문 검사 함수
		if (cnt >= 2) return 2;  // 수정 횟수가 2 이상이면 일반 문자열
		if (start >= end) return cnt;  // 검사 완료 시 cnt 반환
		
		if (stringArray[start] == stringArray[end]) return find(start+1, end-1, cnt);  // 문자가 같으면 다음 문자 검사
		else return Math.min(find(start+1, end, cnt+1), find(start, end-1, cnt+1));  // 문자가 다르면 한 문자 제거 후 검사
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 최악의 경우 각 문자열에 대해 두 번의 회문 검사를 진행하므로 O(2N)이 될 수 있다. 여기서 N은 문자열의 길이를 의미한다. 각 테스트 케이스에 대해 이 작업을 반복하므로 전체 복잡도는 O(T * 2N)이 된다. T는 테스트 케이스의 수다.

느낀점

이 문제를 통해 회문과 유사 회문을 판별하는 방법을 효과적으로 구현하는 방법을 학습할 수 있었다. 투 포인터 기법과 재귀적 접근을 사용하여 문제를 해결하는 과정에서 문자열 처리 기술과 재귀 함수의 효율적 사용법에 대해 깊이 이해할 수 있었다.