SW Expert Academy 15758_무한 문자열 문제풀이 in C++

2022년 11월 11일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

SWEA : 15758_무한 문자열

문제 요구사항

---

• 문자열 S에 대해, f(S)를 S를 무한히 반복해서 얻은 문자열이라고 정의하자. 예를 들어 f(“abcd”) = “abcdabcdabcdabcd…” 이다.
• S≠T이라도 f(S)=f(T) 일 수 있다. 예를 들어 S = “ababab”, T = “abab”라면 f(S)와 f(T) 모두 “ababababababab…”이다.
• 두 개의 문자열 S와 T가 주어질 때, f(S)=f(T)인지의 여부를 구하는 프로그램을 작성하라.

[입력]

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 테스트 케이스는 한 개의 줄로 이루어지며, 각 줄에는 두 개의 문자열 S와 T가 공백 하나를 사이로 두고 주어진다.
• S와 T는 알파벳 소문자(a-z)로만 구성되어 있으며, 1글자 이상 50글자 이하이다.

[출력]

• 각 테스트 케이스마다, f(S)=f(T)라면 ‘yes’를, f(S)≠f(T)라면 ‘no’를 출력한다.

접근 방법

---

• 입력받은 S와 T 문자열을 반복하여 각각 50길이까지 만들어주고, 두 문자열이 서로 포함 관계 혹은 같은지 확인하고 문제에서 요구하는대로 출력한다.

풀이 순서

---

1. TC를 입력 받고, 해당 TC만큼 for문을 반복한다.
2. input을 입력 받고, 공백을 기준으로 구분해 문자열 S와 T를 저장한다.
3. S와 T를 문자열 길이 50이상이 되도록 반복해 만들고, 이후, 문자열 비교를 통해 문제 요구사항에 해당하는지 확인한다.

소스코드

---

#include <iostream>
#include <string>

using namespace std;

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

	int TC;
	cin >> TC;
	cin.get();

	for (int test_case = 1; test_case <= TC; test_case++) {
		string input;
		getline(cin, input, '\n');

		string s = input.substr(0, input.find(' '));
		string t = input.substr(input.find(' ') + 1, input.length() - 1);

		int s_size = s.length();
		int t_size = t.length();
		while (s.length() <= 50) {
			for (int i = 0; i < s_size; i++) {
				s += s[i];
			}
		}

		while (t.length() <= 50) {
			for (int i = 0; i < t_size; i++) {
				t += t[i];
			}
		}

		if (s.length() > t.length()) {
			if (s.find(t) == string::npos)
				cout << "#" << test_case << " no\n";
			else
				cout << "#" << test_case << " yes\n";

		}
		else if (s.length() < t.length()) {
			if (t.find(s) == string::npos)
				cout << "#" << test_case << " no\n";
			else
				cout << "#" << test_case << " yes\n";
		}
		else {
			if (s.compare(t) == 0)
				cout << "#" << test_case << " yes\n";
			else
				cout << "#" << test_case << " no\n";
		}

	}

	return 0;
}

문제 풀이 결과

---