[BOJ] 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의 값을 출력하시면 됩니다.

풀이

문제에 주어진 예제가 너무 부실해서(…) 새로운 예제를 가져왔습니다

6 6 abcdef abcdef abcdef abcdef ggcdef ggcdef

이 예제의 답은 3입니다. count가 3일때 중복되는 문자열 gg가 나오기 때문인데요

이 때 문자열 gg는 길이 2인 문자열입니다.

여기서 문자열 길이가 1일 때 중복을 찾는다면 당연히 중복이 나오게 되고 (g와 g)

길이가 3일 때에는 중복이 나오지 않게 됩니다.

중복이 나오는 길이와 나오지 않는 길이의 경계를 찾는다면 문제를 해결할 수 있겠다는 생각이 들죠?!

그 경계를 binary search로 찾아주면 해결되는 문제였습니다.

#include <string>
#include <cstdio>
#include <map>
#include <iostream>

using namespace std;

int n, m;
char input[1010][1010];
map <string, int> mp;

bool isjb(int size) { //중복있으면 true 아니면 false
	mp.clear();
	for (int col = 0; col < m; col++) {
		string tmp = "";
		for (int row = size + 1; row < n; row++) {
			tmp.push_back(input[row][col]);
		}
		if (mp.count(tmp) == 0) mp[tmp] = 1;
		else return true;
	}
	return false;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &input[i][j]);
		}
	}
	int s = 0, e = n - 1, mid, answer = n - 1;
	while (s <= e) {
		mid = (s + e) / 2;
		if (isjb(mid)) {
			e = mid - 1;
			if (answer > mid) answer = mid;
		}
		else {
			s = mid + 1;
		}
	}
	printf("%d", answer);
	return 0;
}

count를 찾기 위해 binary search를, 중복되는 문자열을 체크하기위해 map을 사용하였습니다.