[백준]2179: 비슷한 단어(javascript)

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

2179번: 비슷한 단어

문제

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

입력

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

출력

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

예제 입력 1 

9
noon
is
lunch
for
most
noone
waits
until
two

예제 출력 1 

noon
noone

---

풀이

javascript의 object로 입력을 받았습니다.

key : index / value : 값

입출력 부분

input = [];
let index = 0;
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    if (N === 0) {
      N = parseInt(line);
      return;
    }
    input.push({
      key: index++,
      value: line,
    });
  })
  .on("close", () => {
    solution(input);
    process.exit();
  });​

input 배열을 value기준으로 오름차순으로 정렬해줍니다.

input.sort((a, b) => {
    return a.value > b.value ? 1 : -1;
  });

이후 문제의 로직은 다음과 같습니다.

1) 접두사의 길이를 구한다.

2) 접두사의 길이를 max와 비교하여 max보다 클 경우 갱신해준다.

3) 접두사의 길이가 max와 같다면 문제의 조건에 맞는 index가 앞선 경우를 갱신해준다.

 

1) 접두사의 길이를 구한다.

const getSameWordLength = (str1, str2) => {
  const len = Math.min(str1.length, str2.length);
  let cnt = 0;

  for (let i = 0; i < len; i++, cnt++) {
    if (str1.charAt(i) !== str2.charAt(i)) {
      return cnt;
    }
  }
  return cnt;
};

- 현재 문자열 2개중 더 짧은 것을 기준으로 처음부터 같지 않은 단어가 나올때까지 index, cnt를 증가시켜주다가 같지 않을 때 cnt를 반환해줍니다.

- 만약 짧은 문자열을 기준으로 모두 같을 수 있으므로 마지막에도 return을 추가해줍니다.

 

2) 접두사의 길이를 max와 비교하여 max보다 클 경우 갱신해준다.

if (max < len) {
        max = len;
        const [minKey, maxKey] = [Math.min(idxI, idxJ), Math.max(idxI, idxJ)];

        ans = [minKey, maxKey];
      }

- max보다 길이가 크므로 무조건 갱신 돼야 합니다.

- 두개의 index중 작은값을 minKey,  큰 값을 maxKey에 넣어줍니다.

 

3) 접두사의 길이가 max와 같다면 문제의 조건에 맞는 index가 앞선 경우를 갱신해준다.

이 문제가 까다로웠던 이유인 것 같습니다.

else if (max === len) {
        const [minKey, maxKey] = [Math.min(idxI, idxJ), Math.max(idxI, idxJ)];

        if (ans[0] > minKey || (ans[0] === minKey && ans[1] > maxKey)) {
        	ans = [minKey, maxKey];
        }
      }

- 두개의 길이가 같은경우는 두가지 조건을 만족할때 갱신되어야 합니다.

1) ans[0](작은 index)가 > minKey(현재 작은 키) 보다 클 때 = 현재가 더 앞선 index이므로 갱신해줍니다.

2) ans[0] == minkey 즉, 현재 앞자리 index는 서로 같지만 ans[1] > maxKey 뒷자리 index가 더 앞설 수 있다면 갱신해줍니다.

 

전체 코드

let N = 0;

const solution = (input) => {
  input.sort((a, b) => {
    return a.value > b.value ? 1 : -1;
  });

  let max = -Infinity;
  let ans = [];
  for (let i = 0; i < N - 1; i++) {
    for (let j = i + 1; j < N; j++) {
      const { key: idxI, value: StringI } = input[i];
      const { key: idxJ, value: StringJ } = input[j];

      if (StringI.charAt(0) !== StringJ.charAt(0)) break;
      const len = getSameWordLength(StringI, StringJ);
      if (max < len) {
        max = len;
        const [minKey, maxKey] = [Math.min(idxI, idxJ), Math.max(idxI, idxJ)];

        ans = [minKey, maxKey];
      } else if (max === len) {
        const [minKey, maxKey] = [Math.min(idxI, idxJ), Math.max(idxI, idxJ)];

        if (ans[0] > minKey || (ans[0] === minKey && ans[1] > maxKey)) {
          ans = [minKey, maxKey];
        }
      }
    }
  }
  console.log(input.find((object) => object.key === ans[0]).value);
  console.log(input.find((object) => object.key === ans[1]).value);
};

const getSameWordLength = (str1, str2) => {
  const len = Math.min(str1.length, str2.length);
  let cnt = 0;

  for (let i = 0; i < len; i++, cnt++) {
    if (str1.charAt(i) !== str2.charAt(i)) {
      return cnt;
    }
  }
  return cnt;
};
input = [];
let index = 0;
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    if (N === 0) {
      N = parseInt(line);
      return;
    }
    input.push({
      key: index++,
      value: line,
    });
  })
  .on("close", () => {
    solution(input);
    process.exit();
  });