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

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

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의 값을 출력한다.

예제 입력 3 

4 6 mrvica mrvica marica mateja

예제 출력 3

1

---

풀이

예제3 입, 출력으로 예를 들어보겠습니다.

문제는 각 행을 한 줄 씩 지워나가는데 각 열을 끝까지 모두 이었을때 중복이 없는 경우를 찾아야합니다.

여기서 저는 이 배열을 회전해보자! 라는 힌트를 얻었습니다. 예제 입력3을 예로 들어보겠습니다.

원본	90도 회전	내가 필요한 값
mrvica mrvica marica mateja	m m m m r   r  a   a v   v   r   t i   i    i   e a  a  a  a	m m m r  a   a v   r   t i   i   e a  a  a

90도 회전을 시켜준다면 바로바로 m m m m > m m m > m m > m순으로 문자열을 확인하기 매우 편해집니다. 또, 문제에서 첫 줄은 반드시 성립한다는 조건이 있기때문에 첫 열은 제외시켜준게 제가 필요한 값입니다.

 

<90도 회전하는 코드 >

for(int i=0; i<C; i++) {
	for(int j=1; j<R; j++) {
		arr[i][j-1] = tmp[j][i];
	}
}

이후 구현은 HashMap에 끝까지 삽입 후 HashMap의 크기가 R의 크기와 같은지 확인하면 됩니다.

//R크기 1 줄여주기
R--;
for(int i=0; i<R; i++) {
	HashMap<String, String>map = new HashMap<>();
	for(int j=0; j<C; j++) {
		String str = String.valueOf(arr[j], i, R-i);
		map.put(str, "");
	}
	if(map.size() == C) cnt++;
	else {
		System.out.println(cnt);
		isFinish = true;
		break;
	}
}

코드

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

public class BJ_G5_2866_문자열잘라내기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        char[][] tmp = new char[R][C];
        char[][] arr = new char[C][R-1];
        int cnt = 0;
        boolean isFinished = false;

        for(int i=0; i<R; i++) {
            tmp[i] = br.readLine().toCharArray();
        }
        //문자열 90도 회전
        for(int i=0; i<C; i++) {
            for(int j=1; j<R; j++) {
                arr[i][j-1] = tmp[j][i];
            }
        }
        //R크기 1 줄여주기
        R--;
        for(int i=0; i<R; i++) {
            HashMap<String, String>map = new HashMap<>();
            for(int j=0; j<C; j++) {
                String str = String.valueOf(arr[j], i, R-i);
                map.put(str, "");
            }
            if(map.size() == C) cnt++;
            else {
                System.out.println(cnt);
                isFinished = true;
                break;
            }
        }
        if(!isFinished) System.out.println(cnt);
    }
}