[백준] 2866 문자열 잘라내기 - Java

 

 

 

인덱스 0부터 시작해서 문자열을 잘라내면서 접근하면 시간 초과가 발생한다.

빠르게 탐색할 수 있는 방법을 생각해야 한다.

 

임의의 k번째 인덱스부터 탐색을 시작한다고 생각해보자.

k번째 인덱스에서 중복이 발생하면, 그 이후 인덱스에 대해서도 당연히 중복이 발생한다.

 

즉, 중복이 발생한 이후에는 쭉 중복이 발생한다.

 

이 부분에 집중하면, 이분 탐색으로 해결할 수 있다는 결론이 나온다.

 

 

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

public class Main {

	static char[][] arr;
	static int R;
	static int C;

	static HashMap<String, Integer> hm = new HashMap<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		arr = new char[R][C];

		for(int i=0; i<R; i++){
			String str = br.readLine();
			for(int j=0; j<C; j++){
				arr[i][j] = str.charAt(j);
			}
		}		

		System.out.println(BinarySearch());
		
	}

	static int BinarySearch(){
		int Left = 1;
		int Right = R -1;
		int ans = 0;

		while(Left <= Right){
			int mid = (Left + Right) / 2;
			if(check(mid)){
				ans = mid;
				Left = mid + 1;				
			}else{
				Right = mid - 1;
			}
		}

		return ans;

		
	}

	static boolean check(int start){

		for(int i=0; i<C; i++){
			String temp = "";
			for(int j=start; j<R; j++){
				temp = temp + arr[j][i];
			}
			if(!hm.containsKey(temp)){
				hm.put(temp, 1);
			}else{
				return false;
			}
		}

		return true;
		
		

	}

}