취미로 코딩하기

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

이번에 볼 문제는 백준 4542번 문제인 Blue Jeans이다.
문제는 아래 링크를 확인하자.

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

각 문자열마다 찾을 수 있는 길이 len의 부분문자열을 각각 모아둔 set을 N개 만들고, 한 set의 원소를 길이가 긴 순으로, 같은 길이면 알파벳순으로 살펴보면서 그 원소가 다른 set에 모두 들어있는지를 확인하자. 이 때, 가장 빨리 위의 조건을 만족하는 문자열이 문제의 답이 된다.

길이가 3 이상인 정답이 없을 경우에는 "no significant commonalities"를 출력해야한다는 조건을 놓치지 말자.

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

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

int N;
string s[10];
set<string> st[10];

void solve() {
	cin >> N;
	for (int k = 0; k < N; k++) cin >> s[k];
	for (int len = 60; len > 2; len--) {
		for (int k = 0; k < N; k++) st[k].clear();
		for (int i = 0; i <= 60 - len; i++) {
			for (int k = 0; k < N; k++) {
				st[k].insert(s[k].substr(i, len));
			}
		}
		for (auto& cur : st[0]) {
			bool chk = 1;
			
			for (int k = 1; k < N; k++) {
				if (st[k].count(cur) == 0) chk = 0;
			}
			if (chk) {
				cout << cur << '\n';
				return;
			}
		}
	}

	cout << "no significant commonalities" << '\n';
}

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

	int T; cin >> T;
	while (T--) solve();
}