문제
만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.
어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다.
예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.
단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.
접근법
일단 문제가 너무 이해하기 힘들게 해놨음..
- a -> z : 그 다음에 나오는 a는 무조건 z로 바꿔야 하고, a를 제외한 다른 알파벳들은 z로 바꿀 수 없음
- b -> b : 자기 자신으로 바꾸는건 가능하기 때문에 b를 제외한 다른 알파벳들은 b로 바꿀 수 없음
ex) zbxz / opor
- z는 처음 등장했고, o도 쓴 적이 없기 때문에 z -> o로 바꿀 수 있음
- b는 처음 등장했고, p도 쓴 적이 없기 때문에 b -> p로 바꿀 수 있음
- x는 처음 등장했지만, o는 이미 썼기 때문에 바꿀 수 없음
- z는 z -> o로 바꾼 전적이 있기 때문에 무조건 o로만 바꿀 수 있기 때문에 r로 바꿀 수 없으니 끝
풀이
let result = 0;
//a를 a로 바꿨다고 할 수 있음
//한번 바꾼 알파벳은 뒤에서는 못 씀
//똑같은 알파벳이 있으면 그건 전부 똑같은 걸로만 or 자기 자신으로만 바꿀 수 있음
for (let i = 1; i < input.length; i++) {
let first = input[i];
for (let j = i + 1; j < input.length; j++) {
let second = input[j];
let isUsed = [];
let map = new Map();
let isMatch = true;
for (let z = 0; z < first.length; z++) {
let [a, b] = [first[z], second[z]];
//기존에 변경한 값이 있으면 - 그 값과 b가 같다면 넘어가기 - 틀리면 끝
//기존에 변경한 값이 없으면 - b가 isUsed에 들어있지 않으면 세팅하고 넘어가기
//들어있으면 - 끝
if (map.get(a) && map.get(a) !== b) {
isMatch = false;
break;
}
if (!map.get(a) && isUsed.includes(b)) {
isMatch = false;
break;
} else if (!map.get(a) && !isUsed.includes(b)) {
map.set(a, b);
isUsed.push(b);
}
}
result += isMatch ? 1 : 0;
}
}
console.log(result);
a가 기존알파벳 , b가 바꾼알파벳으로 놓고
map에는 알파벳을 어떤 알파벳으로 바꾸었는지를 저장하고
isUsed에는 사용한 알파벳을 저장해놓음
'코딩테스트 연습' 카테고리의 다른 글
프로그래머스 - 입국심사 JS (0) | 2023.07.16 |
---|---|
프로그래머스 - 부대복귀 JS (0) | 2023.06.26 |
백준 2309 - 일곱 난쟁이 JS (0) | 2023.06.16 |
프로그래머스 Lev 2 - 숫자 변환하기 (0) | 2023.06.11 |
프로그래머스 - 문자열 나누기 (0) | 2023.06.05 |