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

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

2866번: 문자열 잘라내기

 

 

[난이도] Gold5
[유형] 정렬

[풀이]
각 열 문자로 만든 문자열을 뒤집고 vector에 넣고 정렬해줍니다.
정렬을 해주면 다음과 같은 입력이 주어졌을 때,

mrvica
mrvica
marica
mateja

아래와 같이 정렬이 됩니다.
0:aaaa
1:aarr
2:eiii
3:jccc
4:mmmm

문제의 조건은 결국 위 vector에서 인접한 문자열 두 문자열을 앞에서부터 비교했을 때,
같은 부분이 가장 긴 문자열의 길이를 찾으면 됩니다.

위의 예에서 0번과 1번을 비교했을 때, aa 이므로 이 값을 행의 길이에서 빼주고 1을 빼주면 됩니다.

 

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int r,c,k,mv;
string s[1000];
int main(){
    cin >> r >> c;
    for(int i=0;i<r;i++) cin >> s[i];
    vector<string> st(c);
    for(int j=0;j<c;j++)
        for(int i=r-1;i>=0;i--) st[j].push_back(s[i][j]);

    sort(st.begin(),st.end());
    for(int i=0;i<c-1;i++){
        int k=0;
        for(int j=0;j<r;j++){
            if(st[i][j]==st[i+1][j]) k++;
            else break;
        }
        mv=max(k,mv);
    }
    cout << r-mv-1;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2866.cpp