[BOJ/Gold 5] 백준 2866 문자열 잘라내기(C++)

문제 링크

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

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의 값을 출력한다.

예제 입력 1

2 6
dobarz
adatak

예제 출력 1

0

예제 입력 2

3 4
alfa
beta
zeta

예제 출력 2

2

예제 입력 3

4 6
mrvica
mrvica
marica
mateja

예제 출력 3

1

알고리즘 분류

• 자료 구조

풀이

우선 처음 C개의 문자열은 중복되는 문자열은 주어지지 않는다. 따라서 먼저 문자열의 0번째 원소를 지운다.

이후 R-1번동안, set 자료구조를 사용하여 중복되는 문자열이 있는 지 판별한다. 중복되는 문자열이 없다면 C개의 문자열들 각각의 0번째 원소를 지우고 카운트를 1 올린다. 중복되는 문자열이 존재한다면 해당 과정을 멈추고 바로 카운트를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int R, C;
string Str[MAX][MAX];
vector<string> Vec;
int Answer = 0;

void Input() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < C; j++) {
			Str[i][j] = S[j];
		}
	}
}

void Settings() {
	for (int i = 0; i < C; i++) {
		string S = "";
		for (int j = 0; j < R; j++) {
			S += Str[j][i];
		}
		Vec.push_back(S);
	}
	for (int i = 0; i < Vec.size(); i++) {
		Vec[i].erase(Vec[i].begin());
	}
	for (int i = 0; i < (R - 1); i++) {
		set<string> SET;
		bool Flag = true;
		for (int j = 0; j < Vec.size(); j++) {
			if (SET.find(Vec[j]) == SET.end()) {
				SET.insert(Vec[j]);
			}
			else {
				Flag = false;
				break;
			}
		}
		if (Flag) {
			for (int j = 0; j < Vec.size(); j++) {
				Vec[j].erase(Vec[j].begin());
			}
			Answer++;
		}
		else {
			break;
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}