1216번 - 회문2

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
   1-1. 링크
   1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 문제 링크

SW Expert Academy

 

1-2. 문제 해석

1215번 - 회문1 문제를 조금만 응용하면 쉽게 통과할 수 있는 문제다.

회문1 에서는 길이를 정해주고 그 길이에 맞는 회문이 몇 개 있는지 리턴했으니

이걸 이용해서 for문을 100부터 1까지 쭉 돌며 길이를 주고 그 길이에 맞는 회문이 단 한 개라도 있으면 리턴하면 된다.

 

 

아래 내용은 시간 복잡도를 줄이려 시도하다가 실패한 방법입니다.
시간 많으신 분들은 참고해서 시도해보세용 (될 것 같긴 함!)

 

간단하게 통과해서 코드를 좀 더 업그레이드할 수 없을까 생각해봤다.

시간 복잡도가 O(n³)이 되므로 굉장히 비효율적이라는 생각이 들었기 때문이다.

그래서 다음과 같은 규칙을 이용해보았다.

 

1. 만약 길이가 n인 회문이 있다면 n-2, n-4, n-6... n-m인 회문도 존재한다.
   • 길이가 6인 AABBAA 회문이 있다면 -> 길이가 4인 ABBA, 길이가 2인 BB가 존재한다.
   • 길이가 7인 AABCBAA 회문이 있다면 -> 길이가 5인 ABCBA, 길이가 3인 BCB, 길이가 1인 C가 존재한다.
2. 만약 길이가 n인 회문이 있다면 n-1, n-3, n-5... n-m인 회문의 존재 여부를 확정할 수 없다.
   • 길이가 4인 ABBA 회문이 있다. 하지만 이 회문과 관련 없이 다른 줄에서 길이가 3인 회문이 있을 수도 없을 수도 있다.
3. 만약 어떤 짝수 n에 대하여 회문이 존재하고, 홀수 n-1은 회문이 존재하지 않다면 가장 긴 회문은 짝수가 될 것이다.
   • n보다 큰 홀수 길이의 회문이 존재한다면 1번 규칙에 따라 n-1 길이의 회문도 존재했을 것이다.

 

써놓고 보니까 당연한 말을 괜히 어렵게 적어놓은 것 같다.

아무튼 이 규칙을 잘 적용해서 이진 검색을 시도해보려고 했다.

될 것 같은데...! 잘 안되면서 복잡하게 꼬여버려서 결국 실패했다.

이거만 되면 시간 복잡도를 O(n²)으로 줄일 수 있을 텐데 아까비...! 😩

 

 

2. 코드

public class Day3_1216_회문2 {
	static final int N = 100;
	static char[][] arr = new char[N][N];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int tc = 1; tc <= 10; tc++) {
			StringBuilder sb = new StringBuilder();
			Integer.valueOf(br.readLine());

			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < N; j++) {
					arr[i][j] = str.charAt(j);
				}
			}
			sb.append("#").append(tc).append(" ").append(searchMaxLen());
			System.out.println(sb.toString());
		}
	}
	
	public static int searchMaxLen() {
		for(int i=N; i>0; i--) {
			if(hasRowPalindrome(i)) return i;	
		}
		
		return 1;
	}
	
	public static boolean hasRowPalindrome(int len) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= N - len; j++) {
				if(isColPalindrome(i, j, len)) return true;
				if(isRowPalindrome(j, i, len)) return true;
			}
		}
		
		return false;
	}

	public static boolean isColPalindrome(int y, int x, int len) {
		for (int k = 0; k < len / 2; k++) {
			if(arr[y][x + k] != arr[y][x + len - 1 - k]) return false;
		}
		return true;
	}
	
	public static boolean isRowPalindrome(int y, int x, int len) {
		for (int k = 0; k < len / 2; k++) {
			if(arr[y + k][x] != arr[y + len - 1 - k][x]) return false;
		}
		return true;
	}
}

 

 

3. 실행시간

4등이긴 4등인데...

 

4등이지만 시간 차이가 너무 많이 난다.

아무래도 시간 복잡도가 너무 컸던 탓인 듯하다.

여유만 있으면 좀 더 붙잡고 해 볼 텐데 하루하루 밀려드는 싸피 수업과 과제들...