[LeetCode] Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/

 

여러 개의 단어가 들어간 배열이 주어지고,

각 단어의 앞에서부터 모든 철자끼리 서로 동일한 철자를 갖는 만큼만 출력하는 문제.

예를 들어서.. flow, flower, flawless 라는 세 단어가 주어졌을 때, "fl" 만 출력해야 한다.

 

개어려웠지만.. 어떤 힌트도 보지 않고 혼자 해내서 매우 뿌듯하다.

 

우선은, for문을 돌려서 각 단어별로 순서대로 철자를 하나씩 점검한다.

var longestCommonPrefix = function (strs) {
  //몇 번씩 for문을 돌려줄 지 정하는 부분
  var shortestWord = [];
  var answer = ""; //결과
  for (x = 0; x < strs.length; x++) {
    shortestWord.push(strs[x].length); //가장 짧은 철자를 가진 단어의 길이만큼만 돌려 주어도 되니까
  }
  jmax = Math.min(...shortestWord); //jmax를 가장 짧은 단어의 길이로 설정해 준다.

이 때 for문을 돌리는 횟수는 배열 속의 가장 짧은 단어만큼만 돌리도록 해 줬다. (나름 효율 생각해봄)

그 이후로는 뭐.. 점검해서 같을 수가 없을 뿐더러.. 나머지 단어끼리 같은 것도 의미가 없으니~.~

shortestWord라는 빈 배열을 만들고, 그 안에 각 단어의 길이를 순서대로 넣어 준다.

그리고 Math.min함수를 이용해서 jmax를 가장 짧은 단어의 길이로 지정해 준다.

 

  for (j = 0; j < jmax; j++) {
    var k = 0;
    var strs1 = [];
    for (i = 0; i < strs.length; i++) {
      strs1.push(strs[i][j]);
    }
    console.log(strs1);

그리고  strs1이라는 빈 배열에, 각 단어의 같은 위치(순서)의 철자를 차례대로 넣어 준다.

flow, flower, flawless의 경우 ["f", "f", "f"] , ["l", "l", "l"], ["o","o","a"] 등이 만들어 진다.

이후에 또 for문을 사용해서 각 배열에 들어 있는 철자가 모두 동일한 지 점검해 준다.

동일하지 않을 경우에는 isEqual값을 false로 변경해 주고, true로 남아 있으면 answer에 더해준다.

배열을 너무 많이 썼나 싶긴 하지만.. 아무튼...

 

그렇게 완성한 건 이 코드!

var longestCommonPrefix = function (strs) {
  //몇 번씩 for문을 돌려줄 지 정하는 부분
  var shortestWord = [];
  var answer = ""; //결과
  for (x = 0; x < strs.length; x++) {
    shortestWord.push(strs[x].length); //가장 짧은 철자를 가진 단어의 길이만큼만 돌려 주어도 되니까
  }
  jmax = Math.min(...shortestWord); //jmax를 가장 짧은 단어의 길이로 설정해 준다.

  for (j = 0; j < jmax; j++) {
    var k = 0;
    var strs1 = [];
    for (i = 0; i < strs.length; i++) {
      strs1.push(strs[i][j]);
    }
    console.log(strs1);
    isEqual = true;

    // 각 배열의 모든 철자가 동일한 지 확인한다.
    for (k = 0; k < strs1.length - 1; k++) {
      if (strs1[k] != strs1[k + 1]) {
        console.log(strs1[k], strs1[k + 1]);
        isEqual = false;
      }
    }
    //isEqual이 true로 남아 있으면, 각 단어의 첫 철자가 일치하는 것.
    if (isEqual == true) {
      answer += strs1[0];
    }
    console.log(isEqual);
    console.log(answer);
  }
  return answer;
};

 

근데 문제가 있었다.

flow, flower, flawless등의 단어를 넣었을 때 기대하는 답은 "fl"인데,

"flw"가 출력되는 것... 가장 짧은 단어인 flow를 기준으로 앞에서부터 4번째 철자까지만 점검은 하지만,

중간에 ["o","o","a"] 에서 for문이 멈추지 않고 마지막으로 겹치는 w까지 넘어가 버린 것...

 

그래서 for문이 모두 돌아가지 않더라도,

중간에 isEqual이 false가 되면 바로 리턴하도록 코드를 변경했다.↓

var longestCommonPrefix = function (strs) {
  //몇 번씩 for문을 돌려줄 지 정하는 부분
  var shortestWord = [];
  var answer = ""; //결과
  for (x = 0; x < strs.length; x++) {
    shortestWord.push(strs[x].length); //가장 짧은 철자를 가진 단어의 길이만큼만 돌려 주어도 되니까
  }
  jmax = Math.min(...shortestWord); //jmax를 가장 짧은 단어의 길이로 설정해 준다.

  for (j = 0; j < jmax; j++) {
    var k = 0;
    var strs1 = [];
    for (i = 0; i < strs.length; i++) {
      strs1.push(strs[i][j]);
    }
    console.log(strs1);
    isEqual = true;

    // 각 배열의 모든 철자가 동일한 지 확인한다.
    for (k = 0; k < strs1.length - 1; k++) {
      if (strs1[k] != strs1[k + 1]) {
        // console.log(strs1[k], strs1[k + 1]);
        isEqual = false;
      }
    }
    //isEqual이 true로 남아 있으면, 각 단어의 첫 철자가 일치하는 것.
    if (isEqual == true) {
      answer += strs1[0];
    }
    if (isEqual == false) {
      return answer;
    }
    // console.log(isEqual);
    // console.log(answer);
  }
  return answer;
};

 

뿌듯쓰~~~