백준 2866번 : 문자열 잘라내기

 문제

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

2866번: 문자열 잘라내기

2866 문자열 잘라내기

 

 구현 방법

문제 이해하는데 한참 걸렸습니다..🥺

 

문제는 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만든 다음 그 문자열에서 중복을 찾아내는 것입니다.

처음에는 행을 훑고 그 다음 열을 훑으면서 문자열을 StringBuilder에 하나씩 추가했습니다.
문자열이 만들어지면 set에 값이 있는지 검사하여 중복되면 끝내주고 중복되지 않는다면 set에 추가했습니다.
하지만... 시간초과가 났습니다..

기존 코드는 행 반복문을 돌리고 해당 행마다 열을 계속 탐색하여 문자열을 만드는데 사실 문자열을 계속 겹칩니다.
따라서 행이 0일 때 열을 위에서 아래로 훑어서 초기 문자열을 먼저 만든 다음에 행 반복문을 돌리고 만든 문자열을 잘라가며 사용해주었습니다.

 

 구현 코드

package BOJ.Gold;

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

public class B2866_문자열잘라내기 {
	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[][] word = new char[R][C];
		for (int r=0;r<R;r++) {
			word[r] = br.readLine().toCharArray();
		}
		
		Set<String> set;
		StringBuilder sb;
		int cnt = 0;
		String[] arr = new String[C];
		
		for (int c=0;c<C;c++) {
			sb = new StringBuilder();
			for (int r=1;r<R;r++) { // 제일 윗행은 중복될 일이 없으므로 1부터 탐색
				sb.append(word[r][c]);
			}
			arr[c] = sb+"";
		}
		
		stop:for (int r=0;r<R;r++) {
			set = new HashSet<>();
			for (int c=0;c<C;c++) {
				String now = arr[c].substring(r); // substring 함수를 통해 초기 문자열을 잘라가며 사용
				if (set.contains(now)) break stop; // 문자열이 중복되면 그만!
				else set.add(now);
			}
			cnt++;
		}
		System.out.println(cnt);
	}
}

 

정답!