[BOJ 28064 // C++] 이민희진

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 28064번 문제인 이민희진이다.
문제는 아래 링크를 확인하자.

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

28064번: 이민희진

두 이름 s1과 s2가 있을 때, 두 이름이 연결가능한지를 판단할 수 있다면 이를 N(N-1)/2가지 순서쌍에 적용해보는 것으로 문제를 해결할 수 있을 것이다. 이 판단방법을 생각해보자.

 

두 문자열의 공통 부분 길이 len이 될 수 있는 정수는 1 이상 min(s1의 길이, s2의 길이) 이하이다. 각 후보 len에 대하여 s1의 앞 len개 문자로 구성된 문자열과 s2의 뒷 len개 문자로 구성된 문자열이 같은지, 그리고 s2의 앞 len개 문자로 구성된 문자열과 s2의 앞 len개 문자로 구성된 문자열이 같은지를 각각 확인해 하나라도 같아면 두 문자열을 이어붙일 수 있음을 알 수 있다. 또한 그렇지 않다면 이어붙일 수 없음을 알 수 있다. 이를 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int N;
string s[100];

int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> s[i];

	for (int i = 0; i < N; i++) {
		string& s1 = s[i];
		int s1len = s1.length();
		for (int j = i + 1; j < N; j++) {
			string& s2 = s[j];
			int s2len = s2.length();
			int len = min(s1len, s2len);
			bool chk = 0;
			for (int l = 1; l <= len; l++) {
				if (s1.substr(0, l) == s2.substr(s2len - l, l)) chk = 1;
				if (s2.substr(0, l) == s1.substr(s1len - l, l)) chk = 1;
			}

			if (chk) ans++;
		}
	}

	cout << ans;
}