Maximum width

대회 중에 못풀었던 문제입니다.
문제를 이해하고 풀이를 빠르게 생각해냈지만 계속해서 프리테스트를 통과하지 못했습니다.
rating : 1500
tags : data structures, dp, greedy, two pointers

문제

알파벳 소문자로만 이루어진 길이가 각각 n,m인 문자열 s,t가 주어집니다. t의 각 알파벳의 s에서의 인덱스를 수열 p로 만듭니다. 이 때 1≤p1<p2<…<pm≤n 를 만족해야 합니다. 그러한 수열은 적어도 하나 존재합니다. p[i+1] -p[i]의 최댓값을 구하는 문제입니다.

접근

1. 처음 풀 때
   각 알파벳의 최대 위치, 최소 위치를 구해놓고 {t의 i+1번째 인덱스에 있는 알파벳의 s에서의 최대 위치 - i번째 위치에 있는 알파벳의 s에서의 최소 위치}가 답의 후보라고 생각했습니다.

2. 업솔빙 때
   t의 각 인덱스가 가질 수 있는 s에서의 최소 위치, 최대 위치를 배열에 담아 놓습니다. 그리고 나서 t의 {i+1번째 인덱스의 최대값 - i번째 인덱스의 최소값} 중 최댓값을 선택합니다.

어려움

조건 누락,모호한 설계,구현 오류

답을 제출하니 틀려서 다시 생각해보니 각 알파벳의 최대 위치, 최소 위치를 구해서 답을 구하면 "1≤p1<p2<…<pm≤n" 이 조건을 만족할지 의문이었습니다. t에서 각 알파벳이 가질 수 있는 최소,최댓값의 범위를 한정하는 방식으로 이 문제를 해결하려 했습니다. 범위를 한정하는 것도 맞는 방법같은데 계속 틀렸습니다. 대회를 끝나고 보니 이마저도 구현을 잘못했던 것이 드러났습니다. 구현을 맞게 했어도 인덱스 하나 정도 벗어나지 않을까하는 의문은 계속 들었을 것 같습니다.

"알파벳별로 보는게 아니라 t의 인덱스별로 봐야하네?"하는 것도 구현을 하다가 알게 됐습니다. 이 때부터 엄청 꼬이면서 멘탈이,맞을 가능성이 많이 떨어졌습니다.

피드백

1. 문제 이해 측면
   지문을 보고 조금 어려워 보였습니다. 인덱스에 인덱스를 재참조하는 건 뭔가 어렵게 보이게 만듭니다. 하지만 찬찬히 생각해보고 예제도 보고 해서 문제 이해는 빠르게 했습니다.

2. 설계 측면
   구현을 떠올렸고, 예제를 보니 완벽히 동작해서 7~80% 확신을 가지고 맞겠다 싶어서 구현에 들어갔습니다. 90~100퍼센트 확신은 없었습니다. 완벽히 딱 떨어지는 방법이라는 확신은 안들었습니다.
   구현에 들어가기 전에 의심을 많이 해보고, 딱 떨어지는 방법을 생각해 내야 하는게 맞는거 같은데.. 그런 풀이가 안 떠오를 수도 있어서 지저분하게라도 풀려는 마음이 있었습니다.
   차라리 키보드에서 손을 떼고 다시 알맞은 알고리즘,구현 방식을 떠올리려는 시도를 하는게 낫습니다.

3. 구현 방식
   업솔빙할 때 naive하게 실제로 인덱스를 deque에서 빼는 식으로 구현했습니다. 하지만 그럴 필요없이 투포인터 방식으로 그리디하게 채워넣을 수 있었습니다.

이 정도는 풀 수 있는 문제인데 아쉬움이 많이 남는 문제입니다.

맞은 코드

string s,t;
int n,m; 

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

	cin>>n>>m;
	cin>>s>>t;
	
	vector<int> mn(m),mx(m);
	
	//minimums
	int sidx=0,tidx=0;
	for(;tidx<m;){
		if(s[sidx]==t[tidx]){
			mn[tidx]=sidx;
			sidx++;
			tidx++;
		}else sidx++;
	}
	
	//maximums
	sidx =n-1,tidx=m-1;
	for(;tidx>=0;){
		if(s[sidx]==t[tidx]){
			mx[tidx]=sidx;
			sidx--;
			tidx--;
		}else sidx--;
	}
	
	int mxans=-1e9;
	for(int i=0;i<m-1;i++){
		mxans=max(mxans,mx[i+1]-mn[i]);	
	}
	
	cout<<mxans<<"\n";
	
	
	return 0;
}

첫번째 틀린 코드

int main() {
	int n,m; cin>>n>>m;
			
	string s,t; cin>>s>>t;
	
	vector<ll> mn(30,1e9);
	vector<ll> mx(30,0);
	
	for(ll i=0;i<n;i++){
		int here=s[i]-'a';
		mn[here]=min(mn[here],i+1);
		mx[here]=max(mx[here],i+1);
	}
	
	ll mxans=0;
	for(int i=0;i<m-1;i++){
		
		mxans=max(mxans,mx[t[i+1]-'a']-mn[t[i]-'a']);
	}
	
	cout<<mxans<<'\n';
}