[BaekJoon] 2866 문자열 잘라내기

1.  문제 링크

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

2.  문제

요약

• R개의 행과 C개의 열로 이루어지고 원소가 알파벳 소문자인 테이블이 주어지는데 이 테이블의 열을 위에서 아래로 읽으면 하나의 문자열을 만들 수 있습니다.
• 가장 위의 행을 지우고 나서 남은 테이블의 열을 위에서 아래로 읽어서 나온 문자열들에서 중복되는 문자열이 없다면 가장 위의 행을 지우고 count의 개수를 1 증가시키는 과정을 반복합니다.
• 만약 동일한 문자열이 발견된다면 count의 개수를 출력합니다.
• 테이블이 주어졌을 때 count의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 1000보다 작거나 같은 행의 개수 M과 열의 개수 C가 주어지고 두 번째 줄부터 R개의 줄에 C개의 알파벳 소문자가 주업니다.
• 출력: count의 값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;

public class Main {
	static int row, col;
	static String[][] table;
	
	public int getCount() {
		String[] str = new String[row];
		for(int i = 0; i < str.length; i++) {
			str[i] = "";
		}
		for(int i = 0; i < table.length; i++) {
			for(int j = 1; j < table[i].length; j++) {
				str[i] += table[i][j];
			}
		}
		int count = 0;
		for(int i = 0; i < table[0].length; i++) {
			HashSet<String> set = new HashSet<String>();
			boolean flag = true;
			for(int j = 0; j < str.length; j++) {
				if(!set.add(str[j])) {
					flag = false;
					break;
				}
			}
			if(!flag) {
				break;
			} else {
				count++;
				for(int j = 0; j < str.length; j++) {
					str[j] = str[j].substring(1, str[j].length());
				}
			}
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		col = Integer.parseInt(input[0]);
		row = Integer.parseInt(input[1]);
		table = new String[row][col];
		for(int i = 0; i < col; i++) {
			String temp = br.readLine();
			for(int j = 0; j < row; j++) {
				table[j][i] = temp.substring(j, j + 1);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getCount() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 주어진 테이블에서 열을 위에서 아래로 읽어 나온 문자열들이 중복되는 것이 있는지 확인하면서 중복되는 것이 없다면 count의 값을 1 올리고 해당 문자열들의 가장 앞글자를 제거해주면서 count의 값을 구하는 문제입니다.
• 문자열들이 중복이 되는지 확인하는 방법은 여러가지가 있겠지만 저는 HashSet을 이용하여 중복되는 것이 들어가는지 확인하면서 중복여부를 확인하였습니다.

1. 우리가 필요한 것이 열을 위에서 아래로 읽은 문자열이기 때문에 주어진 행과 열의 개수를 서로 바꿔줘서 2차원 배열을 생성하고 각 행이 우리가 필요로 하는 문자열이 올 수 있도록 입력을 받아줍니다.
2. 각 문자열에서 첫 번째 알파벳을 제외한 문자열들을 구합니다.
3. 문자열의 알파벳 개수만큼 돌면서 중복되는 문자열이 있는지 확인하면서 count를 구합니다.
   1. 중복되는 문자열이 있는지 확인하기 위한 HashSet 하나를 생성하고 중복되는 문자열이 있는지를 표시할 flag라는 불린 타입 변수를 하나 생성합니다.
   2. 2번에서 구한 문자열들을 처음부터 끝까지 HashSet에 추가해보고 만약 중복값이 있어 추가되지 않는다면 flag 변수를 false로 값을 변경해주고 뒤의 문자열들을 확인하지 않고 반복문을 끝냅니다.
   3. 반복문이 완료되었을 때, 만약 flag값이 false라면, 즉 중복되는 값이 있다면 더 이상 가장 위의 행을 지울 수 없으므로 3번의 반복문을 마칩니다.
   4. 만약 flag값이 true라면, 즉 중복되는 값이 없다면 count를 1 증가시키고 모든 문자열들의 처음 알파벳을 해당 문자열에서 제거해줍니다.
4. 3번의 반복문이 끝났을 때의 count값을 출력합니다.