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

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

 

 

 

 

 

풀이)

 

// 2866. 문자열 잘라내기
#include <iostream>
#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
int r, c;
vector<string> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c;
    vec.resize(c, "");
 
    // 문자열을 열이 아니라 행으로 보관한다.
    string temp;
    for (int i = 0; i < r; i++)
    {
        cin >> temp;
        for (int j = 0; j < c; j++)
        {
            vec[j] += temp[j];
        }
    }
 
    // map에 해당 열을 첫글자를 제외하고 넣어준 뒤,
    // 갯수를 세어 원래 vec의 크기와 다르다면
    // cnt를 출력하고 while을 탈출한다.
    int idx = 1;
    int cnt = 0;
    while (1)
    {
        map<string, int> m;
        for (int i = 0; i < vec.size(); i++)
        {
            m[vec[i].substr(idx, vec[i].length() - 1)]++;
        }
 
        if (vec.size() == m.size())
        {
            idx++;
            cnt++;
        }
        else
        {
            cout << cnt;
            break;
        }
    }
 
    return 0;
}
 

---

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

2866번: 문자열 잘라내기