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

문제

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

2866번: 문자열 잘라내기

 

 

사용한 알고리즘

2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)

-> Polynomial Rolling hash 

 

 

 

풀이

1. 이차원 char배열 alphabet에 알파벳을 입력받는다.
2. 열을 거꾸로 올라가며 hash값을 계산해서 hash배열에 담아준다.
   ex.
   배열 alphabet :
   

   m	r	v	i	c	a
   m	a	r	i	c	a
   m	a	t	e	j	a

   배열 hash :
   

   mX^2+mX+m	rX^2+aX+a	vX^2+rX+t	iX^2+iX+e	cX^2+cX+j	aX^2+aX+a
   mX + m	aX + a	rX + t	iX + e	cX + j	aX + a
   m	a	t	e	j	a

3. 각 행을 탐색하며 같은 hash값을 가지는 열이 있는지 확인한다.
   어떠한 행에서 같은 값을 가지는 열이 없으면 count++하고 다음행을 탐색한다.
4. 더이상 행이 없거나 같은 값을 가지는 열이 있으면 --count를 출력한다. 

 

 

 

 

소스코드

#include <iostream>
#include <cstring>

typedef long long ll;
using namespace std;

// Polynomial Rolling hash
#define X 27
// mod 사용 안함

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int R,C; cin>>R>>C;
    // R개의 행과 C개의 열
    int count=0; // 삭제 할 행의 개수
    char alphabet[R][C];
    ll hash[R][C];

    // 1. 이차원 char배열 alphabet에 알파벳을 입력받는다.
    for(int i=0; i<R; i++){
        string tmp; cin>>tmp;
        for(int j=0; j<C; j++){
            alphabet[i][j] = tmp[j];
        }
    }

    // 2. 열을 거꾸로 올라가며 hash값을 계산해서 hash배열에 담아준다.
    for(int j=0; j<C; j++){
        ll POW=1;
        for(int i=R-1; i>=0; i--){
            if(i==R-1)
                hash[i][j] = ll(alphabet[i][j]-'a'+1)*POW;
            else
                hash[i][j] = hash[i+1][j] + ll(alphabet[i][j]-'a'+1)*POW;
            POW *= X;
        }
    }
    
    for(int i=0; i<R; i++){
        int ck=0;
        for(int j1=0; j1<C-1; j1++){
            for(int j2=j1+1; j2<C; j2++){
                if(hash[i][j1]==hash[i][j2]){
                    ck=1;
                    break;
                }
            }
            if(ck) break;
        }
        // 3. 어떠한 행에서 같은 값을 가지는 열이 없으면 count++하고 다음행을 탐색한다.
        if(!ck) count++;
        else break;
    }
    // 4. 더이상 행이 없거나 같은 값을 가지는 열이 있으면 --count를 출력한다. 
    cout<< --count;
    
    return 0;
}