[Javascript] 백준 25957번 단어 우월 효과

1. 문제 설명

문장의 단어들이 특정 규칙에 따라 섞여 있습니다. 각 단어는 첫 번째와 마지막 글자가 고정된 상태에서 나머지 글자의 순서만 섞일 수 있습니다. 주어진 문장의 단어를 원래 단어의 형태로 복원하는 것이 목표입니다.

---

2. 제한 조건

• 원본 단어의 개수 N과 문장의 단어 개수 M은 각각 최대 200,000개.
• 각 단어의 길이는 1 이상 8 이하입니다.
• 각 단어의 첫 글자와 마지막 글자를 제외한 나머지 글자의 배열만 다를 뿐, 동일한 단어는 주어지지 않습니다.

---

3. 해결 방법

알고리즘 분류: 구현, 문자열 처리

1. 고유 키 생성:
   • 각 단어를 고유 키로 변환하기 위해 첫 글자, 마지막 글자, 길이, 정렬된 내부 글자를 조합합니다.
   • 예: bacde → b|e|5|abcde.
2. 원본 단어 저장:
   • 입력받은 원본 단어를 키-값 쌍으로 저장하여 고유 키를 통해 원본 단어를 빠르게 검색할 수 있도록 합니다.
3. 문장 복원:
   • 섞여 있는 문장의 각 단어를 동일한 방식으로 키로 변환한 뒤, 저장된 원본 단어를 검색하여 복원합니다.

---

4. 시간 복잡도

• 원본 단어 저장: O(N×klog⁡k), 여기서 k는 단어의 최대 길이(8)
• 문장 복원: O(M×klog⁡k)
• 총 시간 복잡도: O((N+M)×klog⁡k)

---

5. 구현 코드

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

readline
  .on("line", function (line) {
    input.push(line);
  })
  .on("close", function () {
    const map = new Map();

    const createKey = (str) => {
      return `${str[0]}|${str[str.length - 1]}|${str.length}|${str.split("").sort().join("")}`;
    };

    for (let i = 1; i <= Number(input[0]); ++i) {
      const key = createKey(input[i]);
      map.set(key, input[i]);
    }

    const arr = input[input.length - 1].split(" ");
    const result = arr.map((item) => map.get(createKey(item)));

    console.log(result.join(" "));

    process.exit();
  });