백준 17609번: 회문 [투 포인터][문자열] -Java

 

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

17609번: 회문

자꾸만 "틀렸습니다" 오류나는 분들은

아래 반례를 참고해보세요

1
xyyyyxy


//답은 1이 나와야함

 

 

<Java코드- 실패>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			String str= st.nextToken();
			
			int res = 0; //문자가 다른경우인 횟수
			int idx1 = 0;
			int idx2 = str.length()-1;
			
			while (idx1 <= idx2) {
				//같으면 한칸씩 이동
				if(str.charAt(idx1) == str.charAt(idx2)) {
					idx1++;
					idx2--;
				} else { //다르면 체크
					
					res++; //다른경우 카운트
					if(res>1)
						break;
					
					//다른경우가 한번이라면.. 그래도 기회를 한번 주자
					if(str.charAt(idx1+1) == str.charAt(idx2) && res <2) {
						idx1++;
					} else if(str.charAt(idx1) == str.charAt(idx2-1) && res <2) {
						idx2--;
					}
				}
			}
			
			System.out.println(res);
		}
		
	}
	

}

실패코드는 ... 반례에서 걸린 case이다.

(idx1+1, idx2)와 (idx, idx2-1) 2가지 케이스 모두 같을 수가 있다. 그 경우에 그 사이에 남은 문자에대한 회문을 각각 구해주어야하는데.. 나는 걍 첫 if에서 걸리면 걍 그 case만 보고 퉁쳐버렸다.. 반ㄹㅖ에서 보기 좋게 걸렸다지요

 

					//다른경우가 한번이라면.. 그래도 기회를 한번 주자
					if(str.charAt(idx1+1) == str.charAt(idx2) && res <2) {
						idx1++;
					} else if(str.charAt(idx1) == str.charAt(idx2-1) && res <2) {
						idx2--;
					}

 

 

 

728x90

<Java코드- 투포인터 사용: 성공>

시간복잡도는 머 O(N) .. N이 문자열 길이= 100,000 

isPalindrome은 while문이지만 딱 2번만 돌고 (idx1+1, idx2)와 (idx, idx2-1).. 바로 break 걸리기땜에 N*N이 아님

 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			String str= st.nextToken();
			
			int res = 0; //문자가 다른경우인 횟수
			int idx1 = 0;
			int idx2 = str.length()-1;
			
			while (idx1 < idx2) {
				//같으면 한칸씩 이동
				if(str.charAt(idx1) == str.charAt(idx2)) {
					idx1++;
					idx2--;
				} else { //다르면 체크
					
					//다른경우가 한번이라면.. 그래도 기회를 한번 주자. 
					//앞뒤로 각각 하나 제거했을의 경우 나머지 부분들 회문인지 체크
					if((isPalindrome(str, idx1+1, idx2) || 
							isPalindrome(str, idx1, idx2-1))) {
						//하나 제거하니 회문이네요.. 
						res = 1;
					} else {
						res =2;
					}
						
					break;
				}
			}
			
			System.out.println(res);
		}
		
	}
	
	public static boolean isPalindrome(String str , int l, int r) {

		while(l<r) {
			if(str.charAt(l) != str.charAt(r))
				return false;
			l++;
			r--;
		}
		return true;
	}
	

}