[code kata] week 1 - day 5

week1 - day5

문제

strs은 단어가 담긴 배열입니다.
공통된 시작 단어(prefix)를 반환해주세요.

예를 들어
strs = ['start', 'stair', 'step']
return은 'st'

strs = ['start', 'wework', 'today']
return은 ''

---

정답 풀이

풀이 1

const getPrefix = (strs) => {
  let prefix = '';
  if (strs.length === 0) {
    return prefix;
  }
  for (let i = 0; i < strs[0].length; i++) {
    const key = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][i] !== key) {
        return prefix;
      }
    }
    prefix = prefix + key;
  }
  return prefix;
};

풀이 2

const getPrefix = (strs) => {
  let prefix = strs[0];
  if (strs.length === 0) {
    return '';
  }

  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix === '') {
        break;
      }
    }
  }
  return prefix;
};

실패한 나의 풀이

const getPrefix = (strs) => {
  const arr = [];
  for (i = 0; i < strs.length; i++) {
    arr.push(strs[i].split(''));
  }

  let minStrLen = 1e9;
  for (i = 0; i < arr.length; i++) {
    if (arr[i].length < minStrLen) {
      minStrLen = arr[i].length;
    }
  }

  let guessWord = '';
  let testWord = '';
  for (j = 0; j < minStrLen; j++) {
    for (i = 0; i < arr.length; i++) {
      if (testWord === '') {
        testWord = arr[i][j];
      } else if (testWord === arr[i][j]) {
        continue;
      } else {
        testWord = 0;
      }
    }
    if (testWord !== 0) {
      guessWord.concat('', testWord);
    }
    testWord = '';
  }
  console.log(testWord);
};

console.log(getPrefix(['start', 'stair', 'step']));

---

풀이 1은 내가 떠올렸던 아이디어와 비슷한 방향으로 진행된다. 첫 번째 단어부터 비교해서 나가는 것과

이 문제를 접근할 수 있는 두 가지의 방법이 있다.

1. 첫 글자부터 비교하여 공통되는 글자를 추가하며 진행해 나가는 방법 (풀이 1)
2. 전체 글자를 비교 한 후 공통되지 않는 글자를 하나씩 줄여나가면서 비교하는 방법 (풀이 2)

나는 풀이 1과 비슷하게, 첫글자 부터 비교해서 공통되는 단어를 추가하는 방법으로 진행하려고 했었다.

 

풀이 1은 내가 사용해야 했던 새로운 문법은 없지만, 알고리즘의 구조에 대해서는 생각을 다르게 했어야 했다. 풀이 2도 마찬가지지만, 첫 번째 단어를 기준으로 잡고 문제를 해결하려고 했으면 훨씬 쉽게 풀렸을 것이다. 나는 기준 단어를 잡지 않고 진행을 하려고 하다 보니까 구문이 너무 복잡해졌고, 해결하기 힘들었다.

 

풀이 2에서는 내가 잘 몰랐던 문법을 사용해야 했다.

1. 주어진 문자를 비교하여 찾는 것이므로 .indexOf() 메소드의 활용
2. str 삭제하는 메소드인 .substring() 활용

공통적인 필요 아이디어

1. input값 strs가 빈 배열일 때, ''를 리턴하기
2. 주어진 리스트의 단어 n개의 k번째 글자가 모두 같지 않으면 n-1개의 단어가 같은 것은 의미가 없다. 즉, 단어 하나만 놓고 비교하면 된다.

아직 실력이 부족하다는 것을 많이 느끼게 해주는 문제였다.