이번 글에서는 JavaScript를 활용해 '유사한 문자열 그룹' 문제를 해결하는 방법을 살펴보겠습니다.
문제 정의
두 문자열 str1과 str2는 str1에서 서로 다른 위치에 있는 두 글자를 한 번 교환했을 때 str2와 같아질 수 있다면 유사(similar)하다고 정의합니다. 또한 두 문자열이 완전히 동일한 경우에도 유사한 것으로 간주합니다.
예를 들어, "tars"와 "rats"는 0번째와 2번째 위치의 글자를 서로 바꾸면 같아지므로 유사합니다. 마찬가지로 "rats"와 "arts"도 유사하지만, "star"는 "tars", "rats", "arts" 어느 것과도 유사하지 않습니다.
연결된 그룹의 개념
위 예시의 문자열들은 유사성을 기준으로 다음과 같은 두 개의 연결된 그룹을 형성합니다.
- {"tars", "rats", "arts"}
- {"star"}
여기서 주목할 점은 "tars"와 "arts"가 직접적으로는 유사하지 않지만, "rats"를 통해 간접적으로 연결되어 있기 때문에 같은 그룹에 속한다는 것입니다.
형식적으로 말하면, 어떤 단어가 특정 그룹에 속한다는 것은 그 그룹 내 최소 한 개 이상의 다른 단어와 유사하다는 의미입니다.
문제 요구 사항
문자열 배열 arr이 주어지며, 배열 내 모든 문자열은 서로 애너그램(anagram) 관계입니다. 즉, 모든 문자열은 같은 문자들로 구성되어 있으며 순서만 다릅니다. 우리가 작성해야 할 함수는 이 배열에서 형성되는 그룹의 총 개수를 반환하는 함수입니다.
코드 구현
다음은 위 문제를 해결하는 JavaScript 코드입니다.
const arr = ["tars","rats","arts","star"];
const isSimilar = (str1, str2) => {
const obj = {}
let counter = 0
for(let i=0; i< str1.length; i++){
if(str1[i] !== str2[i]) { counter++ }
obj[str1[i]] = str2[i]
}
return counter === 2 ? true : false
}
const similarStringGroup = (arr = []) => {
const group = [[arr[0]]]
for(let i=1; i<arr.length; i++){
let match = false
for(let j=0; j<group.length; j++){
for(let k=0; k< group[j].length; k++){
const booleanMatch = isSimilar(group[j][k], arr[i])
if(booleanMatch) {
group[j].push(arr[i]);
match = true
break;
}
}
if(match === true) { break }
}
if(match === false){ group.push([arr[i]]) }
}
return group.length
}
console.log(similarStringGroup(arr));코드 설명
isSimilar 함수는 두 문자열을 인덱스별로 비교하여 서로 다른 자리의 개수를 셉니다. 서로 다른 위치가 정확히 2개라면 한 번의 교환으로 두 문자열을 같게 만들 수 있으므로 true를 반환하고, 그렇지 않으면 false를 반환합니다.
similarStringGroup 함수는 첫 번째 문자열로 초기 그룹을 만든 뒤, 나머지 문자열들을 하나씩 순회하며 기존 그룹에 속한 어떤 문자열과도 유사하지 않으면 새로운 그룹을 생성하고, 유사한 문자열이 존재하는 그룹이 있다면 해당 그룹에 추가합니다. 최종적으로 그룹 배열의 길이, 즉 그룹의 개수를 반환합니다.
출력 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
2
결과값 2는 주어진 문자열들이 {"tars", "rats", "arts"}와 {"star"}라는 두 개의 그룹으로 나뉜다는 것을 의미합니다.