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

문제 링크 : https://www.acmicpc.net/problem/2866

이 문제는 Set을 이용하여 구현할 수 있습니다.

문제를 잘 확인해보면 중복되는 경우 반복을 종료합니다. 따라서 Set에서 해당 문자열을 체크한 후 이미 존재한다면 반복을 종료하는 방식으로 탐색합니다.

여기서 중요한 점은 문자열을 입력받을 때 세로 방향으로 읽기 때문에 입력의 인덱스를 반대로 입력받는 것입니다. 그 후 현재 세로줄 위치만큼 문자열을 substring하여 문자열을 잘라낸 후 중복 체크를 진행합니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String[] arr = new String[M];
        for(int i=0;i<N;i++){
            String s = br.readLine();
            for(int j=0;j<M;j++){
                if(i==0) arr[j] = String.valueOf(s.charAt(j));
                else arr[j] += String.valueOf(s.charAt(j));
            }
        }

        if(N == 2){
            System.out.println(0);
            return;
        }

        for(int i=1;i<N-1;i++){
            Set<String> set = new HashSet<>();

            for(int j=0;j<M;j++){
                String key = arr[j].substring(i);
                if(set.contains(key)){
                    System.out.println(i-1);
                    return;
                }
                else set.add(key);
            }

        }
        System.out.println(N-1);
    }
}