BOJ 2866 : 문자열 잘라내기

풀이요약

Set, 이분탐색

풀이상세

Set

1. 문제 해석이 어려웠는데, 여튼 문제는 행을 지워가며 중복이 나오는지 확인하고, 중복이 나올경우 지금까지의 카운트를 출력하는 것이다.

2. 먼저 입력값을 받은 후, 세로 문자열을 만든다. 아마 첫번째 세로 문자열은 무조건 지우고 시작하므로 나의 경우 이 부분은 아예 담지 않았다.

3. 세로 문자열을 탐색하며, 중복 문자열이 없는 경우 카운트 값을 올린 후 다음 계층으로 넘어가 다시 비교를 한다. 예를들어 abc 의 문자열이 있다면 다음 계층에서는 bc 그 다음 계층에서는 c 의 순으로 진행이 된다.

4. 중복 문자열이 나오면 해당 반복문을 종료하고 현재까지의 카운트값을 출력한다.

이분탐색

1. 만약 abc 의 문자열이 중복이 된다면, bc 라는 문자열도 c 라는 문자열도 매 계층마다 중복이 될 것 이다. 그렇다면 임의의 중복 문자열이 발생한 경우, 계층을 늘려 더 긴 길이의 글자를 탐색하고, 그게 아니라면 더 짧은 길이를 탐색하게 한다.

Set

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, ans;
    static char arr[][];
    static String str_arr[];

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        arr = new char[N][M];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().toCharArray();
        }
    }

    private static void toVertical() {
        str_arr = new String[M];
        for (int i = 0; i < M; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 1; j < N; j++) {
                sb.append(arr[j][i]);
            }
            str_arr[i] = sb.toString();
        }
    }

    private static void go() {
        for (int i = 0; i < str_arr[0].length(); i++) {
            Set str_set = new HashSet();
            for (int j = 0; j < M; j++) {
                String str = str_arr[j].substring(i);
                if (str_set.contains(str)) return;
                str_set.add(str);
            }
            ans++;
        }
    }

    private static void output() {
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        toVertical();
        go();
        output();
    }
}

이분탐색

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int N, M, ans;
    static char arr[][];
    static String str_arr[];

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        arr = new char[N][M];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().toCharArray();
        }
    }

    private static void toVertical() {
        str_arr = new String[M];
        for (int i = 0; i < M; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 1; j < N; j++) {
                sb.append(arr[j][i]);
            }
            str_arr[i] = sb.toString();
        }
    }

    private static boolean binarySearch(int mid) {
        Set str_set = new HashSet();
        for(int i=0; i<M; i++) {
            String str = str_arr[i].substring(mid);
            if(str_set.contains(str)) return true;
            str_set.add(str);
        }
        return false;
    }

    private static void go() {
        int l = 0;
        int r = N-1;
        while(l<=r) {
            int mid = (l+r)/2;
            if(binarySearch(mid)) {
                ans = mid;
                r=mid-1;
            } else {
                l=mid+1;
            }
        }
    }

    private static void output() {
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        toVertical();
        go();
        output();
    }
}