BOJ(C++) / 백준 1411 : 비슷한 단어

백준 1411 : 비슷한 단어 

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

1411번: 비슷한 단어

 

🎯 문제

만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.

어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다.

예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.

단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.

 

 

 

🎯 코드

//1411 비슷한 단어
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

bool similar(string s1, string s2) {
	unordered_map<char, char> um;
	unordered_map<char, bool> valid; //알파벳이 사용되었는지 확인
	for (int i = 0; i < s1.size(); i++) {
		if (!um[s1[i]]&& !valid[s2[i]]) {
			um[s1[i]] = s2[i]; //i번째 알파벳 변경
			valid[s2[i]] = true; //사용
		}
		else {
			if (um[s1[i]] != s2[i]) {
				return false;
			}
		}
	}
	return true;
}

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

	int N;
	cin >> N;
	vector<string> v;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		v.push_back(s);
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (similar(v[i], v[j]) == true) {
				answer++;
			}
		}
	}

	cout << answer << "\n";

	return 0;
}

 

🎯 설명

이번 문제는 비슷한 단어를 찾는 문제이다.

예제 입력 1
aa
ab
bb
cc
cd
예제 출력 1
4

예제에서 쌍이 다음과 같이 {aa, bb}, {aa, cc}, {bb, cc}, {ab, cd} 총 4개 존재한다.

 

similar 함수는 두개의 string이 비슷한 단어인지 아닌지 판단하는 함수이다. 

• 해시 맵 unorder_map을 사용하여 각 알파벳이 어떤 알파벳으로 변경되는지 구해야한다.
• 단어의 알파벳을 하나씩 비교한다.
• s1의 알파벳이 바뀐 적이 없을 때는 s2의 알파벳으로 해시 맵(um)에 s2의 알파벳으로 저장해준다.
• s1의 알파벳이 바뀐 적이 있을 때는 해시 맵(um)에 저장 되어있던 알파벳과 s2의 알파벳과 같은지 확인하고 같지 않으면 false를 return한다. 

 

이때 주의할 점은 {ab,bb} 같은 경우는 a에서 b로 변경하면 비슷한 단어로 판단한다.

이 경우를 구분해주기 위해 해시 맵(valid)를 선언하여 판단해주도록 한다. 

• 이전에 변경된 적이 있으면 valid에 변경된 알파벳을 true로 변경해준다.
• 따라서 valid가 true이면 사용할 수 없는 것을 의미하므로 false를 return한다. 
• a가 b로 변경되고 알파벳 b를 true로 변경해주었다. 이후 b는 이미 사용되었기 때문에 비슷한 단어가 아니다.

 

 

고찰

난이도 : Silver 2

오랜만에 블로그 쓰니까 어떻게 쓰는지도 까먹었다... 블로그 자주자주 써야겠다....