백준 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개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않는 입력만 주어진다.

---

처음에 생각한 방법은 테이블의 행을 지우면서 하나씩 문자열을 만들어서 풀었는데, 시간초과가 났다.

다른 분들의 풀이를 보고 , 해결할 수 있었다. 먼저 테이블에서 열을 아래로 읽어서 가장 긴 문자열을 만들어준다.

 

예제에서는 이렇게 테이블이 존재할 경우

dobarz
adatak

da,od,ba,at,ra,zk를 만들어주고, 이 문자열을 문자열의 set에 넣어준다.

 

int r,c;
    cin >> r >> c;
    for(int i = 0;i<r;i++){
        cin >> arr[i]; //문자열을 입력받고
    }
 
    string str[1001];
    for(int i = 0;i<c;i++){ //열의 아래로 내려가는 문자열을 만들고 set에 넣어주기
        set<string> s;
        set<string>::iterator iter;
 
        for(int j = 0;j<r;j++){
            str[i]+=arr[j][i];
        }
 
        s.insert(str[i]);
    }

그 후, 만들어진 문자열에 대해서, 문자열의 처음 부분을 제거해주고 이 문자열이 문자열 set에 있는지 확인한다.

da,od,ba,at,ra,zk에 대해서 첫 문자 d,o,b,a,r,z를 제거한다면, a,d,a,t,a,k가 나오게 된다.

만약 제거해서 나온 문자열이 set에 없다면 set에 넣어주고, set에 존재한다면 중복이 존재하는 경우이므로,

몇번쨰 행인지를 출력해주면 된다.

 

마지막으로 중복이 존재하지 않으면 모든 문자열이 중복이 안되니깐, r-1를 출력해준다.

 for(int i = 0;i<r;i++){
    	set<string> s;
    	set<string>::iterator iter;
 
    	for(int j = 0;j<c;j++){
    		if(str[j].size() != 0){ //빈 문자열이 아닐때, 첫번째 문자를 지워주고
    			str[j].erase(str[j].begin());
 
    			iter = s.find(str[j]); //셋에 존재하는지 확인
    			if(iter == s.end()){ //셋에 존재하지 않으면 셋에 넣어주고
    				s.insert(str[j]);
    			}
    			else{ //셋에 존재한다면 중복되는 문자열
    				if(i == 0){ //몇번째 행인지 출력하고 프로그램 종료
    					cout << 0;
    					return 0;
    				}
    				cout << i;
    				return 0;
    			}
    		}
 
    	}
    }
    cout << r-1; //중복되는 문자열이 없는 경우

---

전체 소스코드->

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main(void){
 
    string arr[1001];
 
    int r,c;
    cin >> r >> c;
    for(int i = 0;i<r;i++){
        cin >> arr[i];
    }
 
    string str[1001];
    for(int i = 0;i<c;i++){
        set<string> s;
        set<string>::iterator iter;
 
        for(int j = 0;j<r;j++){
            str[i]+=arr[j][i];
        }
 
        s.insert(str[i]);
    }
 
    for(int i = 0;i<r;i++){
    	set<string> s;
    	set<string>::iterator iter;
 
    	for(int j = 0;j<c;j++){
    		if(str[j].size() != 0){
    			str[j].erase(str[j].begin());
 
    			iter = s.find(str[j]);
    			if(iter == s.end()){
    				s.insert(str[j]);
    			}
    			else{
    				if(i == 0){
    					cout << 0;
    					return 0;
    				}
    				cout << i;
    				return 0;
    			}
    		}
 
    	}
    }
    cout << r-1;
 
}