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

---

https://www.acmicpc.net/problem/2866

2866번: 문자열 잘라내기

---

• 입력 받은 배열에서 세로 방향으로 문자열을 추출한 후 List에 담는다.
• 위 리스트에서 맨 앞자리를 하나씩 제거하면서 중복된 문자열을 찾는다.

---

[예제 입력1]

dobarz
adatak

// 세로 방향으로 뽑아낸 문자열들
da, od, ba ,at, ra, zk

// 위 리스트에서 맨 앞자리 문자를 하나씩 제거하면서 중복된 문자열을 찾는다.
a, d, a, t, a, k <- 중복 문자열 존재

 

 

 

[예제 입력2]

alfa
beta
zeta

// 세로 방향으로 뽑아낸 문자열들
abz, lee, ftt, aaa

// 위 리스트에서 맨 앞자리 문자를 하나씩 제거하면서 중복된 문자열을 찾는다.
bz, ee, tt, aa	
z, e, t, a

---

[Java]

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main
{

    public static int n,m;
    public static char arr[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new char[n][m];

        // 입력 값 배열 초기화
        for(int i=0; i<n; i++){
            String input = br.readLine();

            for(int j=0; j<m; j++){
                arr[i][j] = input.charAt(j);
            }
        }

        // 배열의 세로 방향으로 뽑은 문자열들을 리스트에 초기화
        ArrayList<String> list = makeList(0);

        // 위 리스트 문자열들의 맨 앞자리를 하나씩 제거하면서 중복이 있는지 체크
        for(int i=1; i<m; i++){
            if(findSame(i, list)){
                bw.write(i-1 + "");
                bw.flush();
                return;
            }
        }

        bw.write(n-2 + "");
        bw.flush();
    }

    // 문자열들을 세로로 뽑은 후 리스트에 추가한다.
    public static ArrayList<String> makeList(int start){
        ArrayList<String> list = new ArrayList<>();

        for(int i=0; i<m; i++){
            StringBuilder sb = new StringBuilder("");
            for(int j=start; j<n; j++){
                sb.append(arr[j][i]);
            }
            list.add(sb.toString());
        }

        return list;
    }

    // 중복되는 문자열이 있으면 true, 없으면 false;
    public static boolean findSame(int start, ArrayList<String> list){
        HashSet<String> hashSet = new HashSet<>();

        for(int i=0; i<list.size(); i++){
            String str = list.get(i).substring(start, n);

            if(hashSet.contains(str))
                return true;
            else
                hashSet.add(str);
        }

        return false;
    }


}