백준 2866 문자열 잘라내기 (Java)

1. 문제 링크

2866번: 문자열 잘라내기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 입력받은 문자들을 세로로 돌면서 문자열을 만든다.

2. 문자열을 하나씩 자르면서 set에 넣는다.

3. set에 동일한 문자열이 들어있다면 끝

 

인데 메모리랑 시간이랑 너무 크게 나와서 이분 탐색으로 다시 풀어봤다.

중복이 없으면 더 뒤로 가야하니까 end을 mid +1로 바꾸고

중복이 있으면 앞으로 가야하니까 start를 mid -1로 바꿨다.

(뒤에서부터 자르니까 start를 뒤로 잡았고, end를 앞으로 잡고 풀었다.)

 

4. 코드

1) 기본 (메모리 307,340KB, 시간 1,276ms)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int R = Integer.parseInt(split[0]);
		int C = Integer.parseInt(split[1]);
		String str;
		int result= 0;
		char[][] map = new char[R][C];
		for (int i = 0; i < R; i++) {
			str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		String[] ing = new String[C];
		StringBuilder sb;
		for(int i=0;i<C;i++) {
			sb = new StringBuilder();
			for(int j=1;j<R;j++) { //첫 줄은 중복 없다니까~
				sb.append(map[j][i]);
			}
			ing[i] = sb.toString();
		} //세로로 문자열 만들어서 저장
		
		HashSet<String> set;
		out: 
		for(int i=0;i<R;i++) { //길이만큼 잘라보자
			set = new HashSet<>();
			for(int j=0;j<C;j++) { 
				str = ing[j].substring(i);
				if(set.contains(str)) {
					break out;
				}
				else {
					set.add(str);
				}
			}
			result++;
		}
		
		System.out.println(result);
	}
}

 

2) 이분 탐색 (메모리 47,120KB, 시간 348ms)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int R = Integer.parseInt(split[0]);
		int C = Integer.parseInt(split[1]);
		String str;
		int result= 0;
		char[][] map = new char[R][C];
		for (int i = 0; i < R; i++) {
			str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		String[] ing = new String[C];
		StringBuilder sb;
		for(int i=0;i<C;i++) {
			sb = new StringBuilder();
			for(int j=1;j<R;j++) { //첫 줄은 중복 없다니까~
				sb.append(map[j][i]);
			}
			ing[i] = sb.toString();
		} //세로로 문자열 만들어서 저장
		
		HashSet<String> set;
		int end = 0;
		int start = R-1;
		while(end <= start) {
			int mid = (start+end)/2;
			set = new HashSet<>();
			for(int j=0;j<C;j++) { 
				set.add(ing[j].substring(mid));
			}
			if(set.size()==C) { //중복이 없는 경우
				end = mid + 1;
			}
			else { //중복되는 경우
				start = mid - 1;
			}
		}
		
		System.out.println(end);
	}
}