[C++] BOJ(백준) 2179 비슷한 단어

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

2179번: 비슷한 단어

 

문자열 문제다.

 

두 단어의 비슷한 정도를 접두사의 길이로 비교하여 가장 비슷한 두 단어를 찾는 문제다.

답으로 S와 T라는 문자열을 출력한다고 했을 때, 우선 순위는 먼저 입력된 순이다.

S와 T가 될 수 있는 문자열이 여러개라면 가장 앞쪽에 위치한 단어가 S,

S가 같다면 T를 기준으로 판단한다.

 

접두사의 공통부분을 찾기 위해 입력단에서 문자열과 인덱스를 벡터에 저장했다.

벡터에 저장한 이유는 정렬을 위해서다.

정렬을 하면 인접한 문자열부터 비슷한 정도를 판단하면 된다.

유사도가 같은 문자열 쌍이 여러개 나올 수 있으므로 가장 앞 쪽에 위치한 쌍을 찾기 위해 인덱스도 함꼐 저장한다.

정답 쌍에 마지막 문자열이 포함되는 경우 정답 갱신이 이루어지지 않는 경우를 막기 위해

정렬 후 마지막에 알파벳이 아닌 다른 문자열을 넣어 끝임을 알렸다.

 

문자열 비교 로직은

1, 현재 인덱스의 문자열과 이후 인덱스의 문자열들을 비교한다.

2. 두 문자열의 공통부분을 찾는다.

이 공통 부분과 이후 인덱스로 인한 4가지 분기문이 갈린다.

1) 처음 비교에서 공통부분이 이전 최댓값보다 이상이면

    - 이전 최댓값보다 큰 경우 무조건 갱신해야 하므로 check 변수를 true

    - 이전 최댓값과 같은 경우 더 앞쪽에 위치한 문자열 쌍을 갱신해야 하므로 check 값을 변경하지 않음

    tmp 벡터를 초기화하고 현재 비교한 두 문자열의 인덱스를 벡터에 추가한다.

2) 처음 비교에서 공통부분이 이전 최댓값보다 작다면 break

3) 처음 이후 비교에서 이전 최댓값과 같다면 해당 문자열의 인덱스를 tmp 벡터에 삽입하고 반복문을 계속한다.

4) 처음 이후 비교에서 이전 최댓값보다 작다면 res 벡터를 갱신한다.

    res 벡터가 비어 있거나 check가 true라면 반드시 갱신한다.

    check가 false라면 이전 최댓값과 유사도가 같으므로 우선순위를 비교한다.

(그 뒤 문자열과 현재 문자열의 공통부분이 더 많을 수는 없음)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, ma;
string arr[20000];
vector<pair<string, int>> v;
vector<int> res;
vector<int> tmp;

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	sort(v.begin(), v.end());
	v.push_back({ "-", 1000000000 });

	for (int i = 0; i < n; i++) {
		bool check = false;
		for (int j = i + 1; j <= n; j++) {
			int index = 0;
			while (index < v[i].first.size() && index < v[j].first.size())
				if (v[i].first[index] == v[j].first[index]) index++;
				else break;
			if (j == i + 1 && ma <= index) {
				if (ma < index) check = true;
				ma = index;
				tmp.clear();
				tmp.push_back({ v[i].second });
				tmp.push_back({ v[j].second });
			}
			else if (j > i + 1 && ma == index) tmp.push_back({ v[j].second });
			else if (j > i + 1 && ma > index) {
				if (res.empty() || check) {
					res = tmp;
					tmp.clear();
					break;
				}

				sort(res.begin(), res.end());
				sort(tmp.begin(), tmp.end());

				if (arr[tmp[0]] == arr[tmp[1]]) {
					tmp.clear();
					break;
				}

				if (res[0] > tmp[0]) res = tmp;
				else if (res[0] == tmp[0]) {
					if (res[1] > tmp[1]) res = tmp;
				}

				tmp.clear();
				break;
			}
			else if (j == i + 1 && ma > index) break;
		}
	}
	sort(res.begin(), res.end());
	cout << arr[res[0]] << "\n";
	cout << arr[res[1]] << "\n";
}