[백준 알고리즘] 2866번 : 문자열 잘라내기

문제

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

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

dobarz
adatak

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

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

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

입력

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

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

출력

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

코드

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

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

        int row = Integer.parseInt(st.nextToken());
        int column = Integer.parseInt(st.nextToken());

        char[][] word = new char[row][column];
        for (int i = 0; i < row; i++) {
            word[i] = br.readLine().toCharArray();
        }

        String[] makeWord = new String[column];
        for (int i = 0; i < column; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j < row; j++) {
                sb.append(word[j][i]);
            }
            makeWord[i] = sb.toString();
        }

        int count = 0;
        stop:
        for (int i = 0; i < row; i++) {
            HashSet<String> hashSet = new HashSet<>();
            for (int j = 0; j < column; j++) {
                String now = makeWord[j].substring(i);
                if (hashSet.contains(now)) break stop;
                else hashSet.add(now);
            }
            ++count;
        }
        System.out.println(count);
    }
}

풀이 및 느낀점

hashSet을 사용했다.

hashSet은 중복된 값을 저장할 수 없다는 특징이 있다. 만들어진 단어들이 hashSet에 있다면, 증가시킨 count값을 바로 출력한다. 하지만 없다면, hashSet에 만들어진 단어를 저장하고 다음 만들어진 단어를 탐색한다.

참고자료