백준 2866 문자열 잘라내기

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

2866번: 문자열 잘라내기

신촌 알고리즘 캠프 초급, 2주차 마지막 연습문제

 

이 질문들을 보면 다들 문제를 이해하는데 엄청 오래걸린 것 같다.

 

문제의 입력으로는 행, 열의 크기와 

그 다음 줄부터는 줄마다 문자열로 각 행이 주어진다.

 

각 열을 하나의 독립된 문자열이라고 하고, 맨 위의 행부터 시작해서 한 행씩 지워가며

문자열의 중복을 검사하고, 중복이 없는 경우 count를 1 증가 시키고 다음 행을 다시 검사한다.

 

중복이 생기는 경우, 해당 연산을 종료하고 count를 출력한다.

 

<풀이>

 

처음에는 단순히 각 열의 마지막 원소에 대한 Hashing 으로 접근했는데 시간 초과가 나왔다..

그래서 2차, 3차 Hash 함수를 작성해서 풀어볼까 생각하다가, 

문자열이 m이라는 행부터 중복인 경우, 당연히 그 아래 행들의 원소 역시 중복이라는 점에서 아이디어를 얻어

 

이분 탐색을 문자열 비교에서 이용하면 mid 부터 검사했는데 중복이 아닌 경우, 그 뒤를,

만약 중복인 경우, 그 앞으로 이동해서 검사를 반복하면 훨씬 쉽게, 그리고 n^2 시간 내에 처리가 가능하겠다

생각이 들어 , 이분 탐색과 간단한 Hash를 적용해서 풀었다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
using std::vector;

char arr[1001][1001];
vector <int> v[26];

int max_cnt = 0, r, c;

void cmp(int idx1, int idx2, int start, int end) {
	
	int result = 0;
	int mid = 0;
	while (start <= end) {
		mid = (start + end) / 2;
		if (!strcmp(&arr[idx1][mid], &arr[idx2][mid])) {
			// 일치하는 경우?
			// start를 더 전진시켜서 확인?
			result = mid - 1;
			end = mid - 1;
		}
		else {
			// 불일치
			// 현재까지 구한 최대와 앞으로 구할 수 있는 가능성을 비교
			start = mid + 1;
		}
	}
	if (max_cnt)
		max_cnt = min(max_cnt, result);
	else
		max_cnt = result;
}

int main(void) {

	int cnt = 0;
	int i, j;
	scanf("%d %d", &r, &c);
	getchar();

	// (j, i)의 형태로 입력
	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			scanf("%c", &arr[j][i]);
		}
		getchar();
	}

	int idx;
	// hash table 적용
	for (i = 0; i < c; i++) {
		idx = arr[i][r-1] - 'a';
		v[idx].push_back(i);
	}

	for (j = 0; j < 26; j++) {
		if (v[j].size() > 1) break;
	}
	if (j == 26) {
		// 중복 하나도 없는 경우,
		printf("%d", r - 1); return 0;
	}

	// 이분 탐색으로 접근 가능?
	// 어떤한 지점 n부터 중복이면
	// 그보다 아래 부분은 당연히 모두 중복이다.

	int cur_idx, cmp_idx;
	
	for (j = 0; j < 26; j++) {
		for (int k = 0; k < v[j].size(); k++) {
			cur_idx = v[j][k];
			for (int x = k + 1; x < v[j].size(); x++) {
				cmp_idx = v[j][x];
				cmp(cur_idx, cmp_idx, 0, r-1);
			}
		}
	}

	printf("%d", max_cnt);

	return 0;
}