백준 BOJ 20191 - 줄임말

한국정보올림피아드 곧응부 문제를 하나씩 풀기 시작해보고 있습니다.

그래도 고등부 상은 있어야지 ㅠㅠ

 

1번치고 상당히 어려웠던 문제지만

적당히 풀어내는데 성공했습니다.

 

www.acmicpc.net/problem/20191

20191번: 줄임말

서브태스크의 조건은 위와 같습니다.

문제를 딱 보자마자 떠오른 풀이는 O(NM)의 풀이로, 이 풀이를 사용하면 42점을 긁어낼 수 있습니다.

( N = S.length()-1, M = T.length()-1 입니다. )

 

S와 T를 입력 받은 다음, 0 ~ S.length()-1까지 순회를 싹 해줍니다.

이 변수를 i로 둘게요.

i로 두고 순회를 시키면서,

T의 인덱스 역할을 해줄 포인터 ptr을 하나 만든 다음,

ptr을 쭉 증가시키면서 만약 S[i] == T[ptr]인경우 i를 1증가시킵니다

(매칭을 성공했으므로)

 

만약 T.length() == ptr이 되어 더이상 순회가 불가능할 경우,

문자열 T를 한번만 붙여서는

S를 만들 수 없다는 뜻이 되므로,

ptr을 다시 초기화하고 ans의 값을 늘려줍니다.

 

하지만 이렇게 푼다면 42점밖에 긁지 못하고,

좀 고민한 끝에 생각한 것은

어차피 O(N)은 고정적으로 지출하게 될 시간 복잡도이니,

M을 줄이자 라는 결론에 도달했고,

M을 전처리해보기로 합니다.

 

배열 K[a][b]를 만들어주는데, K[a][b]는 문자열 T에서 a번째 이후로 등장하는 문자 b의 idx값입니다.

문자 b가 등장하지 않는 경우에는 -1로 넣어주었습니다.

이 배열 K는 O(M^2)에 만들 수 있고,

이 배열을 만든 뒤 포문 내에서는 순회하며 문자를 찾을 필요 없이, K배열에 미리 처리된 인덱스로

바로 건너뛸수 있게 되어 O(N + M^2)가 됩니다.

이 풀이의 경우는 76점까지 긁어낼 수 있습니다.

 

24점을 더 긁기 위해서는

누가봐도 M^2를 더 줄여야 할거같이 생겼습니다.

배열 idx[a][b]를 만들어 줬는데, idx[a]는 문자 a가 등장하는

모든 인덱스값들을 뒤에 쭉 저장해두고있습니다.

인덱스값들의 길이가 전부 다르기 때문에

선언을

vector<int> idx[256] 으로 해주었습니다.

 

이 idx배열의 내용을 채우는데 O(M)이 걸립니다.

전 별도로 배열 정렬도 해줬는데, 지금생각해보니 안해도될지도?

아무튼 정렬도 해준다면 O(MlogM)이 걸립니다.

 

이다음 a부터 z까지의 K배열을 하나씩 채워 나가야 하는데,

idx배열을 적극적으로 써먹어야 합니다.

idx배열의 인덱스들도 단조증가하고,

우리가 찾고있는 T의 포인터 ptr도 단조증가 하기 때문에,

ptr값이 커지면 무조건 idx의 인덱스도 증가해야만 합니다.

 

idx의 인덱스 또한 변수로 만든 다음, 각각의 ptr에 대해서

idx[i][ptr] < j 를 만족하는 최소의 ptr을 찾은 다음,

ptr이 만약 문자열의 길이를 벗어난다면 찾을수없었던 것이므로 -1으로 채워주고,

아닐경우 K[j][i]를 idx[i][ptr]로 처리해주면

O(M)에 가깝게 문제를 해결해줄 수 있습니다.

 

이 경우의 최종 시간복잡도는 상수가 잔뜩 붙은(생략된) O(N+M)이 되고,

AC를 받을 수 있습니다.

 

소스코드를 원하시지 않는분도 있을거같아서

접어두겠습니다

소스코드

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int K[123456][256];
int chkS[256] = {0};
int chkT[256] = {0};
int ans=1;
int ptr=0;

vector<int> idx[256];

int main(){
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	
	string S,T;
	cin >> S >> T;
	
	for(int i=0; i<S.length(); i++) chkS[S[i]]=1;
	for(int i=0; i<T.length(); i++){chkT[T[i]]=1; idx[T[i]].push_back(i);}
	
	int tmps=0;
	int tmpt=0;
	for(int i='a'; i<='z'; i++){
		sort(idx[i].begin(), idx[i].end());
		tmps+=chkS[i];
		tmpt+=chkT[i];
	}
	if(tmps==1 && chkS['a'] && tmpt==1 && chkT['a']){ // case #1 
		printf("%d\n", (S.length()+T.length()-1)/T.length());
		return 0;
	}
	
	memset(K, -1, sizeof(K));
	for(int i='a'; i<='z'; i++){
		ptr=0;
		if(!idx[i].size()) continue;
		for(int j=0; j<T.length(); j++){
			while(ptr < idx[i].size() && idx[i][ptr] < j) ptr++;
			if(ptr == idx[i].size()) K[j][i] = -1;
			else K[j][i] = idx[i][ptr];
		}
	}
	
	ptr=0;
	for(int i=0; i<S.length(); i++){
		if(chkT[S[i]] == 0){ puts("-1"); return 0; }
		re:;
		//printf("[%d위치에서 %c의 idx는 %d입니다]\n", ptr, S[i], K[ptr][S[i]]);
		if(K[ptr][S[i]] == -1){
			ans++;
			ptr=0;
			goto re;
		}else{
			ptr = K[ptr][S[i]]+1;
		}
	}
	printf("%d", ans);
	return 0;
}

여담

아니 무슨 1번이 이렇게 어려워요?

2년 PS안한동안

도대체 정올에 무슨일이있었으면

1번부터

난이도가

이렇게

어렵죠????