[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을 사용하였습니다.