[알고리즘 - 백준] 13397번 구간 나누기2(java)

백준 문제 링크

이 문제는 left = 0, right = 'arr 배열 중 가장 큰 값' 이렇게 설정해놓고 이분탐색을 통해 문제를 해결할 수 있다.

중간값인 mid = (left+right)/2 가 될 것이고, mid값이 타당한지 계속 체크해준다. 어떻게 타당한지 체크하는가 ?

1. range = 1, minValue, maxValue를 arr[0]으로 세팅해놓고 arr[n-1]까지 for문을 돌면서 최소와 최댓값을 갱신시켜준다. 이때 range는 구간을 말한다. arr[0]부터 arr[n-1]까지 돌건데, 첫번째 구간이라는 의미에서 range = 1로 초기화한 것이다.

2. 이때 maxValue-minValue가 mid보다 크다면 범위를 넘어가는 것이므로 range++을 해주고 minValue, maxValue를 Integer.MIN_VALUE, Integer.MAX_VALUE로 초기화해준다. 하던 for문을 마저 돈다.

3. range 값(구간의 갯수)를 리턴한다.

이렇게 mid값이 타당한지에 대한 함수를 돌려주고 range값과 M을 비교해서, M보다 작거나 같다면 right = mid-1로, 만약 M보다 크다면 left = mid+1로 바꿔준다,

이때 left<=right을 만족하는 경우만 while을 반복하므로 left>right 인 순간 탈출하게 된다. 따라서 이때의 right값이 최댓값의 최솟값이 된다.

여러 블로그를 참고해보았지만 이 이상으로 이해하기는 어려웠고 다음의 이분탐색 문제를 풀때 참고해볼만한 풀이라고 생각하고 넘어갔다.

import java.util.*;
import java.io.*;
class Main{
	static String arr[][];
	static int R, C, count;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		arr = new String[R][C];
		for(int i=0;i<R;i++) {
			String s = br.readLine();
			for(int j=0;j<C;j++) {
				arr[i][j] = s.substring(j, j+1);
			}
		}
		
		List<String> sList = new ArrayList<>();
		for(int i=0;i<C;i++) {
			String sub1 = "";
			for(int j=0;j<R;j++) {
				sub1 += arr[j][i];
			}
			sList.add(sub1);
		}
		
		for(int i=1;i<R;i++) {
			Set<String> set = new HashSet<>();
			boolean flag = false;
			for(int j=0;j<sList.size();j++) {
				String sub = sList.get(j).substring(i, R);
				if(set.contains(sub)) {
					flag = true; break;
				}else set.add(sub);
			}
			if(flag) break;
			count++;
		}
		
		System.out.println(count);
	}
	
}