[C++] 백준 2866번 : 문자열 잘라내기

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

2866번: 문자열 잘라내기

 

1. 세로단어가 중복되면 stop : map 사용

2. 회차마다 배열에서 char 단위로 세로단어 만들어서 map에 넣고 판별 : 시간초과

3. 최초 입력시 세로단어를 string 배열로 만들어서 회차마다 substr로 map에 넣고 판별 : 통과

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <sstream>
#include <map>

using namespace std;

int r, c;
char arr[1000][1000];
string str[1000];
int cnt = 0;

int main() {
	
	ios::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);

	cin >> r >> c;
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
		}

	for (int i = 0; i < c; i++) {
		for (int j = 0; j < r; j++) {
			str[i] += arr[j][i];
		}
	}

	int cr = 1;
	while (r - cr >= 1) {
		map<string, int> map;
		bool dup = false;

		for (int i = 0; i < c; i++)
			map[str[i].substr(cr, r - cr)]++;

		for (auto m : map) {
			if (m.second > 1) {
				dup = true;
				break;
			}
		}

		if (dup)
			break;
		cnt++;
		cr++;
	}

	cout << cnt;

	return 0;
}