BOJ_2866_문자열 잘라내기 (Java)

[Gold V] 문자열 잘라내기 - 2866

문제 링크

성능 요약

메모리: 304568 KB, 시간: 1100 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 문자열

제출 일자

2025년 3월 2일 21:48:02

문제 설명

R개의 행과 C개의 열로 이루어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다.

각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있다. 예제 입력에서

dobarz
adatak

이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 된다.

만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을 지워주고, count의 개수를 1 증가시키는, 이 과정을 반복한다. 만약 동일한 문자열이 발견되는 경우, 반복을 멈추고 count의 개수를 출력 후 프로그램을 종료한다.

테이블이 주어질 경우 count의 값을 구해보자.

입력

첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000)

이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않는 입력만 주어진다.

출력

문제의 설명과 같이 count의 값을 출력한다.

문제 풀이

모든 문자열을 생각해보고 각 문자열을 행마다 Hashset으로 비교했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb;
    static int R, C;
    static String[] lines;
    static ArrayList<String> words;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2866_문자열잘라내기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        lines = new String[R];
        words = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            lines[i] = br.readLine();
        }

        for(int j = 0; j < C; j++) {
            sb = new StringBuilder();
            for (int i = 0; i < R; i++) {
                sb.append(lines[i].charAt(j));
            }
            words.add(sb.toString());
        }

        Set<String> set;
        for (int i = 0; i < R; i++) {
            set = new HashSet<>();
            for (String s: words) {
                String substring = s.substring(i);
                if(!set.add(substring)) {
                    System.out.println(i-1);
                    return;
                }
            }
        }
        System.out.println(R - 1);
        bw.flush();
        bw.close();
        br.close();
    }
}