[백준2179_자바스크립트(javascript)] - 비슷한 단어

🔴 문제

비슷한 단어

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const n = Number(inputs[0]);
const words = inputs.slice(1);

let maxSameLen = 0;
let q;
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    const s = words[i];
    const t = words[j];

    let currentSameLen = 0;
    for (let k = 0; k < Math.min(s.length, t.length); k++) {
      if (s[k] !== t[k]) break;
      currentSameLen = k + 1;
    }

    if (maxSameLen < currentSameLen) {
      maxSameLen = currentSameLen;
      q = [s, t];
    }
  }
}

if (q.length) {
  console.log(q[0]);
  console.log(q[1]);
} else {
  console.log(words[0]);
  console.log(words[1]);
}

🟢 풀이

⏰ 소요한 시간 : 50분

딱 어떤 유형이라고 하긴 어려운 것 같고 개인적으로는 구현 문제 같았다.
두 단어의 공통부분 문자열의 길이 저장할 변수 maxSameLen을 만들어 주고, 공통부분 문자열이 가장 길 경우 정답을 저장할 큐를 만들어 줬다.
그 후 중첩 반복하면서 비교를 할 두 단어를 선택할 예정인데 i는 0부터 n까지, j는 i부터 n까지 순회를 하면 모든 경우의수를 다 순회할 수 있다.
두 단어가 골라졌으면, 더 길이가 짧은애만큼 반복하면서 같은 인덱스의 문자가 동일한지 확인한다. 만약 같은 인덱스의 문자가 다르다면, 그 때의 k까지가 currentSameLen가 된다.
그 후 currentSameLen과 maxSameLen를 비교해 최대값을 갱신해준다. 이때 정답이 되는 s와 t도 갱신시켜준다.
마지막으로 정답을 출력할 때는 큐에 요소가 있다면 큐의 값을 출력해주면 되고, 큐에 요소가 없다면 words에서 가장 처음나온 두 단어를 출력해주면 된다.

+) 맞았습니다를 받았지만 이 코드는 채점시 2400ms 즉 2.4초가 소요된 코드이다. 이 문제는 2초이내의 시간제한을 가지므로 테스트 케이스가 많아진다면 오답이 된다. 따라서 시작할때 아예 문자열 배열의 첫자를 비교하고 같은 문자로 시작하는 요소들끼리 비교를 하던지 하면 된다.

🔵 Ref