Portfolio

📑 문제

구글에서 많이 출제된 문제입니다

✏️ 풀이

재영

일단 가장 먼저 떠올린 건 N=100000이니까 O(NlogN)안에는 풀어야겠다는 생각이었어요.

1개까지의 오차 허용을 해준다는 점이 가장 중요했어요. 따라서 한 번만 봐주고 그 다음에는 안 봐줬어요. 😄

문자가 100000개일 경우 새롭게 문자를 만드는 것 자체가 꽤나 부하가 일어날 것 같았어요. 따라서 for문으로 하되, ignoreIndex를 만나면 그냥 지나가도록 설계를 해줬어요.

또한 투 포인터를 써서 앞 뒤로 한 번에 for문을 체크해줬어요.

결과적으로 이는 최악의 경우에도 O(1.5N)을 만족하는 듯 싶습니다 :) (0.5N * 3)


const validPalindrome = s => {
  return isPalindrome(s) ? true : false;
}

const isPalindrome = (s, ignoreIndex = undefined) => {
  let wordLength = s.length;
  let front = 0;
  let rear = wordLength - 1;
  for (let i = 0; i < wordLength; i += 1) {
    if (front === ignoreIndex) front += 1;
    if (rear === ignoreIndex) rear -= 1;
    if (s[front] !== s[rear]) {
      if (ignoreIndex !== undefined) return false 
      return (isPalindrome(s, front) || isPalindrome(s, rear)) ? true : false;
    };
    front += 1;
    rear -= 1;
  }
  return true;
}

(() => {
  const s = "abcadaca"
  console.log(validPalindrome(s))
})()

최적화

그래도 뭔가 화났어요. 저기서 ignoreIndex를 저렇게 처리해줘야 돼?!라는 생각이 들었거든요.

따라서 고민한 결과, 제가 놓친 게 있었어요.

어차피 한 번만 바꿀 거면, 그냥 삭제한 자리에서부터 front와 rear를 매개변수로 넣어주어 기억시켜줘도 상관 없을 거 같다는 생각이 들었어요. (기회는 한 번 뿐이니까요!)

그 결과, front, rear 위치로 초기화시킨 다음에 하니, 더욱 빨라졌습니다!

얼추 계산해보니, 최악의 경우에도 O(N)에 가깝게 나오는군요!


const validPalindrome = s => isPalindrome(s);

const isPalindrome = (s, prevFront, prevRear) => {
  let front = prevFront || 0;
  let rear = prevRear || s.length - 1;

  while (rear >= front) {
    if (s[front] !== s[rear]) {
      return (prevRear) // 있으면 사실상 이미 한 번 재귀한 것. false 리턴.
				? false;
	      : isPalindrome(s, front + 1, rear) || isPalindrome(s, front, rear - 1)
    };
    front += 1;
    rear -= 1;
  }
  
  return true;
}

// 84ms, faster than 93.37 %
// 45.9 MB, faster than 89.13 %

효성


var validPalindrome = function(s) {
    
    if(s.length <= 2) {
        return true
    }
    
    let left = 0, right = s.length-1
    
    while(left < right) {
        
        if(s[left] !== s[right]) {
            return isPalindrome(s, left +1, right) || isPalindrome(s, left , right-1)
        }
        left++
        right--
    }
    return true

};

function isPalindrome(str, left, right) {
    while(left < right) {
        if(str[left] !== str[right]) {
            return false
        }
        left++
        right--
    }
    return true
}

매개변수로 주어진 string의 앞, 뒤를 비교하여 같은지 확인한다.

만약 중간값을 제외하고 모든 알파벳이 같으면 true를 return한다.

다만, 일치하지 않는 값이 한 번있을 때 왼쪽 또는 오른쪽 값을 무시하고 나머지가 일치한다면 true를 return한다.

일치하지 않는 값이 두 번 이상일 경우 false를 return한다.

은찬


/**
 * @param {string} s
 * @return {boolean}
 */
const checkPalindrome = (front, back, s) => {
    while(front <= back){
        if(s[front++] !== s[back--]){
            return false;
        }
    }
    
    return true;
}

const validPalindrome = (s) => {
    let front = 0;
    let back = s.length - 1;
    
    while(front <= back){
        if(s[front] !== s[back]){
            return checkPalindrome(front + 1, back, s) || checkPalindrome(front, back - 1, s);
        }
        
        front++;
        back--;
    }
    
    return true;
};

현석

첫 번째 풀이


var validPalindrome = function(s) {
    
    const checkPalindrome = (string, opp) => {
        let start = 0;
        let end = string.length - 1;
    
        if(string.length <= 1) return true;
        
        if (opp < 1 && string[start] !== string[end]) {
            return false; 
        } else if (string[start] === string[end]) {
            return checkPalindrome(string.slice(start + 1, end), opp);
        } else {
            return checkPalindrome(string.slice(start + 1), opp - 1) || checkPalindrome(string.slice(start, end), opp - 1)           
        }
                    
    }
   return checkPalindrome(s, 1)
};

run time: 153 ms, faster than 21.66%
memory usage: 59 MB, less than 5.20%

// 별로 마음에 안드는 풀이

Valid Palindrome II

📑 문제

✏️ 풀이

최적화