[BOJ-17609][그리디] 회문 - Java

문제 바로가기

17609번: 회문

오랜만입니다!!

합격 연락받고 방 구하고 짐싸고 이사하고 출근하고 한다고 정신없는 연말연초를 보내고 오랜만에 노트북 앞에 앉아 보았습니다.

 

실버1이길래 스근할 줄 알았는데 생각보다 쪼끔 까다로웠습니다 ^^;;;;

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		input();
	}
	
	public static int check(String str) {
		if(checkPalindrome(str) == true) return 0;
		else if(checkPseudoPalindrome(str) == true) return 1;
		else return 2;
	}
	
	public static boolean checkPalindrome(String str) {
		int s = 0, e = str.length() - 1;
		
		while(s <= e) {
			if(str.charAt(s++) != str.charAt(e--)) return false;
		}
		
		return true;
	}

	public static boolean checkPseudoPalindrome(String str) {
		int s = 0, e = str.length() - 1;

		while(s <= e) {
			if(str.charAt(s) != str.charAt(e)) {
				// 왼쪽 없애고 난 뒤의 문자열 | 오른쪽 없애고 난 뒤의 문자열 중 하나라도 회문이 있으면 유사 회문
				return checkPalindrome(str.substring(s+1, e+1)) | checkPalindrome(str.substring(s, e));
			}
			
			s++; e--;
		}

		return true;
	}

	public static void input() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());

		while(T-- > 0) {
			bw.write(String.valueOf(check(br.readLine())));
			bw.write("\n");
		}
		
		bw.flush();
		bw.close();
	}
}

 

처음에는 단순히 문자열에서 하나씩 뺀 문자열을 구하고 얘가 회문인지를 체크했는데 시간초과가 떴습니다..

이유가 무엇인고하니 String .equals() 메소드의 시간 복잡도가 O(n)인 것이였슴다... 유사회문인지 체크하기 위해 새로 만든 문자열 O(n) 에 equals() 메소드를 호출하니 O(n^2)가 되는 것이지요..

 

두번째로는 intern() 메소드를 이용하는 방법을 생각햇습니다. 새로 만든 애를 intern()을 호출해서 같은 문자열이 있다면같은 애를 가리키도록 하는 것이지요. 이렇게 해서 .hashCode()의 값이 같은지 여부로 같은 문자열인지 체크했습니다..

하지만 이렇게 하면 String pool 에 문자열이 없다면 새로 만들기 때문에 메모리 초과가 떠버렸습니다...

 

 

그렇게 해서 회문 여부를 체크하는 로직부터 다 뜯어 고쳤습니다. 문자열의 왼쪽/오른쪽 을 비교해나가는 것이져. 회문은 단순히 이렇게 비교해가며 구할 수 있고, 유사 회문은 한 번 기회를 주는 겁니다. 왼/오 서로 다른 문자가 나오면 (왼쪽 애를 제외한 나머지가 회문인지 | 오른쪽 애를 제외한 나머지가 회문인지) 를 체크하는 것이죠. 둘 중에 하나라도 회문이라면 얘는 유사 회문이니깐 or 문으로 묶어씀니다.

 

 

 

역시 꾸준히 하지 않으면 머리도 굳고 손가락도 굳는듯 합니다.

다시 화이팅!!!