[Leetcode Top Interview 150] 125. Valid Palindrome

난이도 : easy 

문제링크

• 주어진 문자열 s가 펠린드롬인지 판별하라
  
  • case-insensitive함
  • 공백이 제거된 상태에서 판별
• 펠린드롬 : 중앙을 기준으로 대칭인 문자열

 

•  1 <= s.length <= 2*10^5
• s는 오직 ascii 문자만 포함함

 

1. 접근법

• 투 포인터를 두어 한 쌍이라도 invalid하다면 false 리턴
• 문자열 끝까지 반복문을 돌려 invalid하지 않다면 true 리턴

 

2. 의사코드

int 처음부터_시작하는_포인터 = 0;
int 맨뒤에서_시작하는_포인터 = s.length-1;

while (처음부터_시작하는_포인터 < 맨뒤에서_시작하는_포인터) {
    if (s[처음부터_시작하는_포인터] 숫자 혹은 알파벳이 아니면) 
      처음부터_시작하는_포인터++;
      
    if (s[맨뒤에서_시작하는_포인터] 숫자 혹은 알파벳이 아니면) 
      맨뒤에서_시작하는_포인터--;

    <펠린드롬 체크>
    if (s[처음부터_시작하는_포인터] != s[맨뒤에서_시작하는_포인터]) {
      return false;
    }            
}

return true;

 

3. 구현 코드

int firstIdx = 0;
int lastIdx = s.length()-1;

int firstAscii;
int lastAscii;
int caseDifference = 'a' - 'A';

while (firstIdx < lastIdx) {
    firstAscii = s.charAt(firstIdx);
    lastAscii = s.charAt(lastIdx);

    while (firstIdx < lastIdx &&
          (firstAscii < '0' || (firstAscii > '9' && firstAscii < 'A') || (firstAscii > 'Z' && firstAscii < 'a') || firstAscii > 'z')
        ) {
        firstAscii = s.charAt(++firstIdx);
    }

    while (firstIdx < lastIdx && 
          (lastAscii < '0' || (lastAscii > '9' && lastAscii < 'A') || (lastAscii > 'Z' && lastAscii < 'a') || lastAscii > 'z')
        ) {
        lastAscii = s.charAt(--lastIdx);
    }          

    if (firstAscii != lastAscii) {   
        if ((firstAscii >= '0' && firstAscii <= '9') || (lastAscii >= '0' && lastAscii <= '9')) {
            return false;
        }

        if (Math.abs(firstAscii - lastAscii) != caseDifference) {
            return false;
        }
    }

    firstIdx++;
    lastIdx--;
}        

return true;

 

• 포인터에서 방문한 문자가 숫자 혹은 문자가 아니면 
  • 첫번째 포인터가 마지막 포인터보다 작을 때까지
    • 첫번째 포인터를 오른쪽으로 이동시키기 
    • 마지막 포인터를 왼쪽으로 이동시키기
• 첫번째 포인터와 마지막 포인터가 가리키는 문자의 아스키 값이 다르다면
  • 둘다 문자열이 아니면 invalid
  • 둘다 문자열이지만 아스키값의 차의 절대값이 caseDifference 값이 아니면 invalid

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - n개 원소까지 반복하므로
• 공간복잡도 : O(1) - n개 원소를 돌아도 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘

 

5. 개선점

잘 모르겠다

 

6. 회고

s = s.toLowerCase();
String alphanumericInput = s.replaceAll("[^A-Za-z0-9]", "");

char[] targets = alphanumericInput.toCharArray();


int left = 0;
int right = targets.length-1;
for(int idx=0; idx < targets.length/2; idx++){
    if(targets[left++] != targets[right--]){
        return false;
    }
}

return true;

(출처 : https://1minute-before6pm.tistory.com/25)

 

다른 분의 풀이를 보았는데

1. 소문자로 모두 바꾸기 (toLowerCase 사용)

2. 숫자, 알파벳이 아닌 문자 모두 없애기 (replaceAll 사용)

3. 왼쪽 포인터 값과 오른쪽 포인터 값 일치 비교 (input 길이의 반만큼만 반복시킴)

 

1, 2는 일부러 사용하지 않았다

1, 2의 내부 동작을 자세히 몰라서였다.

아마 배열 모든 요소를 다 돌텐데 그렇다면 O(n)은 깔고 시작하는거 아닌가?

물론 추가적으로 반복문을 돌아도 O(n + n) 이니까 O(n)이지만 속도면에서 아끼려고 시도하지 않았다

그러나 실전으로 들어가면 저렇게 쓰는게 맞다 생각한다

내장 라이브러리는 사용해도 지장없다 멘토님께서 말씀해 주셨으니까..

또한 내 코드를 짜는데  시간이 오래 걸려서 다음번에는 이렇게 풀면 안되겠다는 생각을 했다 ㅋㅋ

 

3은 반복수를 input 길이의 반만큼만 해도 되나? 라는 생각이 들었으나

left와 right크기를 같은 조건일때 증가량이 같은값이므로(1) 중복검사가 발생해도 괜찮을 것 같다 (코드가 깔끔해져 보기 좋다)