[백준] 2607 비슷한 단어 JavaScript

혅·2025년 3월 28일

백준, 프로그래머스 -JavaScript-

목록 보기

213/215

문제

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

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

예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

출력

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

예제 입력

4
DOG
GOD
GOOD
DOLL

예제 출력

내가 했던 풀이 방법

각각 배열에 구성 요소를 담을 Map이 담긴 N크기의 배열을 선언한다. 즉, 하나의 문자열에 대해 구성 요소 정보가 담긴 Map이 존재한다.
문자열을 하나씩 검사하면서, Map의 구성 요소와 갯수를 담아준다. 즉, "DOG"의 경우 D->1, O->1, G->1이 된다.
0번 문자열에 대해 다른 문자열을 Map을 통해 비교한다. getDiff를 통해 두 문자열의 diff를 반환한다. diff는 두 문자열의 구성요소 차이로 map1을 우선 순회하면서 map2에 해당 문자열이 있을 경우, 두 개수의 차이를 더해주고, map2에 해당 문자열이 없을 경우 count를 diff에 더해준다. map1을 다 돌았어도 map2에서 검사 안 한 문자열이 있을 수 있다. 이때, map1에 존재하는 경우는 위에서 체크했으므로 map2를 순회할 때는 map1에 존재하지 않을 경우만 diff에 count를 더해준다.
3번에서 반환된 diff를 가지고 유사한지를 체크한다. 이때, 두 문자열의 길이가 같다면 diff가 0부터 2까지일 경우, 비슷한 단어가 될 수 있고 두 문자열의 길이가 다르다면 0부터 1까지만 가능하다. 왜냐하면, 하나의 문자를 다른 문자로 바꾸어라는 조건 때문인데 예를 들어 CAT, PAT을 비교할 경우 diff는 2가 된다. 하지만, P를 C로 바꿔주기만 하면 비슷한 문자가 될 수 있다. 즉, 하나의 문자를 다른 문자로 바꾸는 경우에는 diff가 2여도 가능하다. 이때 두 문자열의 길이가 다르면 diff가 2일 때, 하나의 문자를 다른 문자로 바꾸는 게 의미가 없다. 예제에서 언급했듯이 DOG와 DOLL은 diff가 2지만, 하나를 바꾼다고 해서 두 문자가 같아질 수 없기 때문이다.

코드

const fs = require('fs');
let [N, ...str] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
str = str.map((i) => i.trim());

let strMap = Array.from({ length: N }, () => new Map());
for (let i = 0; i < N; i++) {
  let map = strMap[i];
  for (let j = 0; j < str[i].length; j++) {
    if (map.has(str[i][j])) map.set(str[i][j], map.get(str[i][j]) + 1);
    else map.set(str[i][j], 1);
  }
}

function getDiff(map1, map2) {
  let diff = 0;

  for (let [char, count] of map1) {
    if (map2.has(char)) {
      diff += Math.abs(map2.get(char) - count);
    } else {
      diff += count;
    }
  }

  for (let [char, count] of map2) {
    if (!map1.has(char)) {
      diff += count;
    }
  }
  return diff;
}

let answer = 0;
for (let i = 1; i < N; i++) {
  let diff = getDiff(strMap[0], strMap[i]);
  if (str[0].length === str[i].length) {
    if (0 <= diff && diff <= 2) answer++;
  } else {
    if (0 <= diff && diff <= 1) answer++;
  }
}

console.log(answer);