[BOJ/백준 2607][C++] 비슷한 단어

문제

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

 

문제 내용

기준이 되는 단어와 비교했을 때, 비슷한 단어가 몇 개인지 출력하면 된다.

 

먼저 같은 구성을 갖는 기준은 아래와 같다.

1. 두 문자열이 같은 종류의 문자로 이루어져 있다.
2. 같은 문자는 같은 개수만큼 있다.

=> 즉, 문자열을 정렬했을 때 두 문자열이 일치해야 한다.

 

그럼 비슷한 단어의 기준을 알아보겠다.

1. 두 문자열이 서로 같은 구성일 경우
2. 한 문자열에서 한 글자를 삭제하거나, 추가하거나, 다른 문자로 바꾸었을 때, 다른 문자열과 같은 구성이 될 경우

 

문제 풀이

처음에는 문제가 약간 헷갈렸다.

문제를 풀 때 그냥 풀지 말고 생각하고 구현해야 하는 문제 같다.

 

일단, 기준 문자열과 비교 대상이 되는 문자열은 한 글자 차이이거나 길이가 같아야 한다. (당연한 이야기이다.)

입력으로 기준 문자열을 받아, alpha [26] 배열에 각 알파벳이 몇 개나 있는지 파악했다.

이때 base[i]-'A' 이런 식의 코드를 썼는데, base[i]가 알파벳 A이면 'A'-'A'는 0이 되므로, alpha배열의 0번에 A문자의 개수를 입력할 수 있다.

이 방식으로 A~Z의 알파벳 개수를 파악한다.

 

기준 문자열에 대한 처리가 끝나고, 비교 대상이 되는 문자열을 일일이 입력받아 계산해주면 된다.

다만 비교 문자열의 개수가 한개가 아니기 때문에, 기존 문자열의 알파벳 구성인 alpha배열을 복사해서 사용했다.(ccopy배열)

비교 대상이 되는 문자열을 한글자씩 읽어가며, 기준 문자열과 같은 것이 몇 개나 되는지를 파악해 same변수에 저장한다.

 

이제 조건문을 통해 판단하면 된다.

1) 기준 문자열의 길이 == 비교 문자열의 길이

이 경우, 두 문자열이 한글자가 달라도 되고, 아예 구성이 같아도 된다.

즉, same의 값이 0이나 1이면 된다는 의미이다.

 

2) 기준 문자열의 길이-1 == 비교 문자열의 길이

이 경우, 기준 문자열의 길이가 1 큰 경우이다.

그렇기 때문에 비교 문자열에 글자 하나를 추가하면 된다.

단, 추가하기 이전의 구성이 기준문자열의 구성과 하나 차이가 나야 한다.

그래서 이 경우에 same의 값이 기준 문자열보다 1 작아야 한다.

 

3) 기준 문자열의 길이+1 == 비교 문자열의 길이

이 경우, 기준 문자열의 길이가 1 작은 경우이다.

그렇기 때문에 비교 문자열에서 한 글자를 삭제해야 한다.

단, 삭제하기 이전의 구성이 기준문자열의 구성과 동일하면서 다른 문자가 하나 추가된 경우여야 하기 때문에, same의 값이 기준 문자열과 동일해야 한다.

 

코드

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

/*
* 순서는 중요하지 않다.
* 같은 구성을 가질 때 
* +1, -1, 하나 바꿈
*/

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

	//입력
	int n;	cin >> n;
	string base,comp; cin >> base;

	//문제 해결
	int alpha[26] = { 0, }; //알파벳 구성이 어떻게 되어있는지
	int base_len = base.size();
	for (int i = 0; i < base_len; i++) { 
		alpha[base[i] - 'A'] += 1;
	}
	
	int count = 0;
	for (int i = 0; i < n - 1; i++) {
		cin >> comp;
		int comp_len = comp.size();
		int ccopy[26];
		copy(alpha, alpha + 26, ccopy); //배열 복제

		int same = 0;
		for (int i = 0; i < comp_len; i++) {
			if (ccopy[comp[i] - 'A'] > 0) {
				ccopy[comp[i] - 'A']--;
				same++;
			}
		}

		if (base_len == comp_len) { //두개의 길이가 같을 때
			if (same == base_len || same == base_len - 1) {
				//구성이 아예 같거나, 한글자가 다른경우
				count++;
			}
		}
		//기준 문자열이 한 글자 길 때 => 한 글자가 추가
		else if (base_len - 1 == comp_len && same == base_len - 1)
			count++;

		//기준 문자열이 한 글자 짧을 때 => 한 글자 삭제
		else if (base_len + 1 == comp_len && same == base_len)
			count++;
		else continue; 
	}

	//결과 출력
	cout << count << '\n';	
}