[백준] 회문 (골드5, 시간복잡도는 왜 선형을 유지할 수 있을까.. N^2이 아니고?)

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

17609번: 회문

 

설명

 회문(palindrome)은  앞 뒤 문자가 같아, 앞으로 읽어도 뒤로 읽어도 같은 문자가 되는 문자열을 의미한다. 우선 회문의 개념은 알았으니 문제를 좀 살펴보면, O(N^2) 풀이로는 도저히 풀 수 없을 것 같다는 걸 문자열의 범위만을 봐도 알 수 있다. 문자열의 길이는 최대 10만 까지 주어지므로, T개의 케이스를 모두 연산해야 하기 때문에 O(T * N^2) 만큼의 시간이 소요되게 알고리즘을 작성하면 시간초과가 난다.

따라서 이 문제는 투 포인터 알고리즘을 사용해서 풀이할 수 있는데, 초반에 생각이 너무 꼬이면서 일반화 되지 않음에도 불구하고 알고리즘을 작성해서 계속 오답 판정을 받았다. 처음엔 짝수와 홀수의 개수를 보고 몇 개의 예제들에 적용을 해보았지만 계속 반례가 발생했다. 다음으로는 서로 다른 문자를 가진 위치에서, start와 end의 앞 뒤로 앞의 문자 다음 문자가 뒤에 문자와 같은지 혹은 뒤에 문자 다음 문자가 앞의 문자와 같은지를 판단하여 예제 케이스를 모두 통과했지만, 둘 다 가능한 경우를 고려하지 못했고, 이를 고려하기 위해 짝 홀의 개수를 이용해야 되겠다는 생각이 들었지만, 번번이 실패했다.

 

아이디어는 비교적 간단했다. 해당 문제를 정말 간단하게 생각해서 풀 수 있는 해답이 있었는데, 그 아이디어는 다음과 같다. 서로 같은 문자라면 두 개의 포인터를 같이 옮기게 되지만, 서로 같지 않은 문자라면 두 개의 포인터를 옮기지 않고, 서로 다른 문자 중 한 문자를 삭제 한 뒤 회문이 존재하는지 여부를 판단한다. 실제로 이 생각을 유사하게나마 했었지만 나는 문제가 생기는 서로 다른 문자가 있을때의 조건이 시간복잡도에 큰 영향을 준다고 생각했고 그래서 N^2의 시간복잡도를 갖는다고 생각했기 때문에 불가능하다고 생각했었다. 

 

하지만 이는 시간복잡도를 정확하게 계산 해보지 않았기 때문에 불가능한 것이라고 생각했었고, 실제로 시간복잡도를 차근차근 다시 계산한 결과 선형 시간을 유지할 수 있다는 것을 깨닫게 되었다. 그래서 지금부턴 왜 해당 코드가 선형 시간을 유지할 수 있는지에 대해서 설명해보려고 한다.

 

코드

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

public class 회문 {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


	public static boolean isPalindrome(int start, int end, char[] array){
		while (start < end) {

			// 여기서 걸리게 되면, 유사회문을 만들 수 없으므로
			if(array[start] != array[end]) {
				return false;
			}

			start++;
			end--;
		}

		// 그렇지 않다면, 유사회문을 만들 수 있음
		return true;

	}

	public static void run() throws IOException{

		// 케이스
		int T = Integer.parseInt(br.readLine());


		while ( T > 0) {

			String str = br.readLine();
			// 배열로 바꿔준다. ( 문자끼리 검사하기 때문에)
			char [] array = str.toCharArray();

			// start, end
			int start = 0;
			int end = array.length - 1;
			boolean flag = true;
			while (start < end) {

				if(array[start] != array[end]) {
					// 둘중에 하나라도 참이라면, 유사회문이니까
					if(isPalindrome(start+1, end, array) || isPalindrome(start, end - 1, array)){
						System.out.println(1); flag = false; break;
					} else {
						System.out.println(2); flag = false; break;
					}
				}

				start++;
				end--;
			}
			if(flag) System.out.println(0);
			T--;

		}
	}
	
	public static void main(String[] args) throws IOException{
		
		run();
	}
}

 

 자바 코드로 작성한 풀이다. 중요하게 볼 부분은 isPalindrome() 함수에서 다시 한번 while문을 반복하고 있다는 부분이다. 아마 단순히 계산 했다면, 이건 O(N^2) 코드라고 생각이 들 수 있지만, 다음과 같이 생각해 본다면 N^2이 아닌 N을 유지할 수  있다는 것을 생각해 볼 수 있을 것 같다.

 

먼저, 유사회문과 평문이 아닐때 즉 회문일 때를 생각해 보자. 회문일 때는 각 포인터가 가리키는 위치에 서로 같은 문자가 존재하기 때문에, 포인터를 같이 증가/감소시켜 시간복잡도가 O ( N / 2 ) 만큼 루프가 돌아갈 수 있다는 것을 알 수 있다. 왜냐하면 회문임을 가정했기 때문에, 회문인 순간 모든 위치에 모든 알파벳은 서로 같은 위치의 알파벳임을 보장하기 때문이다. 그러므로 start < end는 문자열의 절반인  N / 2만큼 루프가 반복될 수 있다.

왜 모든 위치에 모든 알파벳이 서로 같은 위치에 알파벳임을 보장하냐면 회문은 앞에서 읽든, 뒤에서 읽든 서로 같은 문자가 나오면서 그 뒤로도 똑같이 아무 문제가 없이 읽히게 되면 회문이기 때문이다. 결국 각 포인터들이 가리키는 위치에 똑같은 알파벳이 있다면 앞에서부터 읽어나가는 순서가 뒤에서부터 읽어 나가는 순서와 같기 때문에 보장할 수 있다는 것이다.

 

그럼, 유사회문과 평문일 때를 생각해보자. isPalindrome() 함수가 실행되고, 마찬가지로 start < end까지 탐색하게 된다. 아마 나처럼 안일한 생각을 갖고 시간복잡도를 계산했다면, N^2 시간이 나오는데 이게 어떻게 가능하지? 생각이 들 것이다. 

 

먼저 유사회문일 경우 start + 1 또는 end - 1위치로 옮긴 뒤에, 문자열을 탐색하게 된다. 그럼 아래 두 가지 경우를 좀 생각해 보자.

 

 

유사회문인 경우, 첫 번째 for 문을 계속 루프를 돌게 할 이유가 있는가?
유사회문이 아닌 경우, 첫 번째 for 문을 계속 루프를 돌게 할 이유가 있는가?

 

 

생각을 잘해보면 그 이유가 없다는 걸 알 수 있다. 왜냐하면, 유사회문인 경우를 판단하기 위해서는 현재 위치한 각 포인터가 서로 다른 알파벳이고, 그로 인해 각각의 포인터를 하나씩 옮겼을 때 회문이 가능한지 아닌지를 판단한다. 그렇다면 이미 start + 1 또는 end - 1로 인해, 알파벳이 삭제되었다고 생각해 본다면, 유사회문의 정의가 '단 하나의 문자를 삭제했을 경우' 회문이 만들어지는지 아닌지를 보는 것 이기 때문에 이미 문자는 한 개 삭제되었고, 이후로는 삭제될 문자들이 없어야 한다는 사실을 알 수 있다. 

 

즉 유사회문이라면, isPalindrome() 함수가 한 번만 실행이 되어야 하고, 그 한 번의 루프속에서도, 더 이상의 삭제될 문자가 나오면 안되기 때문에 만약 또 한번의 삭제될 문자가 나왔다면, 유사 회문이 아닌 게 되는 것이고 그렇지 않고 하나만 삭제하고서 루프를 마치게 되었다면 더 이상의 삭제될 문자가 없이 회문 조건을 만족했기 때문에 유사회문이 될 수 있는 것이다. 그러므로 첫 번째 루프에 더 이상 영향을 받지 않고 루프를 종료시켜 유사회문을 검사하는 동안에는 O(N) 선형 시간을 보장할 수 있게 된다. 

 

결국 첫 번째 루프에 영향을 받게 되는 것은 유사회문을 검사할 필요가 없는, 그 자체로 회문인 경우만 첫 번째 루프에 영향을 받게 되며, 그 그렇지 않은 경우 유사회문임을 밝혀야 하는 경우는 첫 번째 루프에 영향을 받을 이유가 사라진다고 볼 수 있다.