[백준] 2179 비슷한 단어 c++

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

 

주의해야 될 조건
1. 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 함
=> 무조건 갱신
2. 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력

접두사의 길이가 같은 경우가 여러개일 때를 살펴보면
=> abcz, abcd, abce, abc 순서대로 입력  -> 답 : abcz, abcd 
abcz가 제일 앞에 있으므로 S, abcd가 그 다음 앞에 있으므로 T 이다.
sort() 후 : abc, abcd, abcde, abcz 가 된다.
즉, 입력 순서 인덱스도 고려해줘야 한다. 

풀이

1. 문자열을 정렬
2. for문을 돌면서 접두사의 길이를 체크
3. 접두사가 지금까지 구한 것보다 더 크면 정답 벡터를 비우고 기록
4. 접두사가 지금까지 구한 것과 같으면 정답벡터에 기록

정답벡터에는 {입력 인덱스, 문자열}
5. 정답 벡터 정렬 -> 입력 인덱스 오름차순으로 정렬됨.
6. S와 T 찾기 : 제일 처음에 오는 것이 S가 된다. 
정답 벡터에는 접두사가 다른 문자열도 들어가 있다. ex) abcd - 0 , efh - 2,efhy - 3, abcz - 4 , abc -5  , (문자열-입력인덱스)
T를 찾을 때에는 접두사가 같은 것을 찾아줘야 한다. 
정답 : abcd, abcz

if (s.substr(0, maxCnt) != ans[i].second.substr(0, maxCnt))
    continue;

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n;
vector<pair<string,int>>v;
int cnt, maxCnt;
string s, t;
string tmp;
vector<pair<int, string>>ans; //인덱스와 겹치는 것 
vector<pair<int, string>>ans2; //인덱스와 겹치는 것 


int main() {
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v[i] = { tmp,i };
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < n - 1; i++) {
		cnt = 0;
		for (int j = 0; j < v[i].first.size(); j++) {
			//같지않으면
			if (v[i].first[j] != v[i + 1].first[j]) {
				break;
			}
			cnt++;
		}

		//두 문자열이 완벽히 똑같으면 답이 될 수 없음
		if (v[i].first == v[i + 1].first || cnt<maxCnt)
			continue;
		//cnt 가 maxCnt 보다 크면 ans 벡터 초기화 
		//cnt가 maxCnt 랑 크거나 같으면 
		if (cnt > maxCnt) {
			ans = ans2;
			maxCnt = cnt;
		}
		
		ans.push_back({ v[i].second,v[i].first});
		ans.push_back({ v[i+1].second,v[i + 1].first});
		
	}
	sort(ans.begin(), ans.end());
	string s = ans[0].second;
	for (int i = 1; i <= ans.size(); i++) {
		if (ans[i].second == s)
			continue;
		if (s.substr(0, maxCnt) != ans[i].second.substr(0, maxCnt))
			continue;
		t = ans[i].second;
		break;
	}
	cout << s << "\n" << t;
	
}

 

다른 풀이

https://www.acmicpc.net/source/80916675

접두사와 입력 인덱스를 map에 저장한다.

문자열의 접두사가 이미 존재할 때 두 가지 케이스로 나눈다.
map에 이미 존재하는 map에 있는 인덱스가 S의 위치 , 현재 인덱스가 T의 위치가 된다.

i) 접두사 길이가 최대일 경우
최대 접두사의 길이를 갱신해준다.