[G4] 백준 2179번 비슷한 단어 C++ 문자열, 브루트포스 알고리즘

리뷰

 

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

트라이로 문제를 접근했는데 모든 예제가 다 맞아도 계속 AC를 받지 못하였다.

브루트포스 알고리즘을 사용하면 최대 2만 * 2만 / 2의 연산이 진행되고 시간 제한이 2초이므로 시도해 보았는데 해당 방법으로 AC를 받았다.

풀고도 찝찝한 문제...

 

전역 변수

• n : 문자열의 개수를 저장할 정수형 변수
• max_len : 탐색 중 접두사의 최대 길이를 저장할 정수형 변수
• a1, a2 : 최대 길이의 접두사를 가진 문자열의 인덱스를 저장할 정수형 변수
• str : 문자열 정보를 저장하기 위한 문자열 타입의 배열, 최대 크기는 2만이다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 문자열을 str배열에 입력 받아준다.
2. 0 ~ n - 2, i + 1 ~ n - 1까지의 2중 for문을 개행해 준다.
3. str[i]와 str[j]의 사이즈를 비교하여 작은 값을 정수형 변수 len에 초기화 해준다.
4. len이 max_len보다 작을 경우 탐색할 필요가 없으니 continue 처리해준다.
5. 현재 문자열간의 접두사의 개수를 세어줄 정수형 변수 cnt를 0으로 초기화 해준다.
6. len길이의 반복문을 개행하고, 두 문자의 k번째 인덱스가 다를 경우 break 아닐 경우 cnt를 증가시킨다.
7. max_len이 cnt보다 작을 경우 cnt로 바꾸어 주고 a1, a2에 각각 i, j를 저장해 준다.
8. 탐색이 완료된 후에 str배열의 a1, a2인덱스를 줄바꿈을 기준으로 출력해 주면 된다.

 

참고 사항

• 브루트포스를 통해 완전 탐색을 돌렸으므로 별도의 정렬은 필요하지 않다.
• 최악의 케이스엔 적용되지 않겠지만 len이 max_len보다 작을 경우 탐색하지 않는 가지치기를 넣어주었다.

 

정답 코드

#include<iostream>
using namespace std;

int n, max_len, a1, a2;
string str[20000];

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

	cin >> n;
	for (int i = 0; i < n; i++) cin >> str[i];

	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int len = min(str[i].size(), str[j].size());
			if (len < max_len) continue;
			int cnt = 0;
			for (int k = 0; k < len; k++) {
				if (str[i][k] != str[j][k]) break;
				cnt++;
			}
			if (max_len < cnt) {
				max_len = cnt;
				a1 = i;
				a2 = j;
			}
		}
	}
	cout << str[a1] << "\n" << str[a2];
}