리트코드 - 125. Valid Palindrome

리트코드 - 125. Valid Palindrome

출처 - https://leetcode.com/problems/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 문자열 s가 팰린드롬(Palindrome)인지 판별합니다. 팰린드롬은 모든 대문자를 소문자로 변환하고, 영숫자문자가 아닌 문자를 제거한 후, 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말합니다. 여기서 영숫자문자(Alphanumeric)는 문자와 숫자를 포함합니다.

문자열 s가 팰린드롬인지 판별하고, 팰린드롬이라면 true를 반환하고 아니라면 false를 반환합니다.

 

의사코드

문자열 중에 영숫자문자가 아니면 제거 문자열을 소문자로 반환 문자열을 배열로 변환 왼쪽  = 0 오른쪽 = 배열 길이 - 1 반복문시작(왼쪽 < 오른쪽)     if 왼쪽 문자 오른쪽 문자 같지 않으면         false 반환         왼쪽 1 증가     오른쪽 1 감소 반복문 종료     true반환

풀이코드

class Solution {
    public boolean isPalindrome(String s) {
        String convertAlphanumeric = s.replaceAll("[^a-zA-Z0-9]","")
                                        .toLowerCase();
        String[] arr = convertAlphanumeric.split("");

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            if (!arr[left].equals(arr[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

코드설명

문자열을 받아 replaceAll을 이용하여 숫자와 문자를 제외하고 공백으로 만들어준다.

여기서 표현된 정규식은 [^a-zA-Z0-9] 이며, 앞에 ^는 부정을 의미하고, a-z는 a부터 z까지, 마찬가지로 A-Z는 A부터 Z까지, 그리고 0-9는 숫자 0부터 9까지를 의미한다.

즉, 영문과 숫자를 제외한 값이 공백이 된다.

 

이후 toLowerCase() 메소드를 이용하여 모든 문자열을 소문자로 바꾸어주고, 이것을 배열에 담는다.

 

다음으로, left 포인터와 right 포인터를 두고 양끝에서 문자열을 조회한다.

만약 left 인덱스와 right 인덱스의 배열 값이 같지 않으면 false를 반환하고, 값이 같으면 left는 +1 right는 -1칸 이동하여 비교한다.

 

최종적으로 값이 같음이 확인되면 true를 반환한다.

 

시간복잡도 - O(log n)

공간복잡도 - O(n) (새로운 배열을 만들 때 모든 값이 영문+숫자일 경우 최대 n)

문제를 풀며 생각한 흐름과 배운 점

문제를 풀며 해결해야할 관심사는 두가지였는데

 

1) 문자열을 어떻게 자를까? 에 대한 부분과

2) 배열을 어떻게 빨리 순회할까? 였다.

 

문자열을 잘라 비교하는 방법

문자열을 잘라서 비교하는 것은 정규식을 이용하는 방법과 charAt() 메소드를 이용하는 방법이 있는데 이번에는 잘 써보지 않은 정규식을 써보고 이번기회에 공부해보기로 했다.

 

String에는 matches() 라는 메소드가 있는데 이 파라미터에는 찾을 string 값을 넣어 존재하는 경우 boolean값을 반환할 수 있다.

이곳에 정규식을 입력해도 비교가 가능한데 이 정규식은 아래와 같다.

 

^[a-zA-Z0-9]*$

 

^는 문자열의 시작을 나타내고 $는 종료를 나타낸다.

[] 는 찾을 문자열을 나타내고, *는 반복을 나타낸다.

 

a-zA-Z0-9 는 코드 설명에서 설명한 부분과 같다.

 

즉, 첫 문자부터 끝 문자까지 괄호 안에 해당하는 문자가 아닌 경우 false를 리턴하고, 아니면 true를 리턴한다.

 

배열을 빨리 순회하는 방법

이번에는 교육에서 배운 투포인터 라는 방법을 사용해보기로 했다.

투 포인터는 맨 앞과 맨 뒤에 각각 포인터를 두고 배열을 앞과 뒤를 동시에 순회하는 방법이다.

투 포인터의 시간복잡도는 O(log n)인데, 이는 n을 (1/2)^n 번 씩 순회하기 때문이다.

class Solution {
    public boolean isPalindrome(String s) {
        if (!s.matches("^[a-zA-Z0-9 ]*$")) {
            return false;
        }
        String[] arr = s.split("");
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            if (!arr[left].equals(arr[right])) {
                return false;
            }
        }
        return true;
    }
}

그래서 위 문자열을 자르는 것과 투포인터를 이용하여 코드를 짰는데 시간초과가 났다.

 

이 코드에서는 잘못된 점이 있는데 첫번째는 s.matches 를 사용하는 부분이었고 두번째는 while문 이었다.

if문의 조건이 영숫자문자가 아니면을 판별하고 있는데 문제에서 주어진 조건은 영숫자문자를 제외하고 영숫자문자만 가지고 앞뒤가 같은 건지 판별하는 것이다. 영숫자문자가 없으면 false를 리턴하니 잘못된 코드다.

 

그리고 while문에서 left와 right를 이동시키지 않았기에 무한루프에 빠져 시간초과가 났다.

 

해당 부분을 적절하게 수정하고 나서 테스트를 통과하게 되었다.

 

다른코드

class Solution {
    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
        	return true;
        }
        int start = 0;
        int last = s.length() - 1;
        while(start <= last) {
        	char currFirst = s.charAt(start);
        	char currLast = s.charAt(last);
        	if (!Character.isLetterOrDigit(currFirst )) {
        		start++;
        	} else if(!Character.isLetterOrDigit(currLast)) {
        		last--;
        	} else {
        		if (Character.toLowerCase(currFirst) != Character.toLowerCase(currLast)) {
        			return false;
        		}
        		start++;
        		last--;
        	}
        }
        return true;
    }
}

이 코드에서는 charAt을 이용해서 직접 string에 접근하고 있는데,

배열을 직접 만들지 않고, chatAt을 사용하여 char 변수만 사용하니 공간복잡도는 O(1)이 된다.

 

그리고 if분기를 보면.... Character.isLetterOrDigit이라는 메소드를 사용하고 있다.

 

이 메소드를 들어가서 찾아가보면 char 형을 파라미터로 받으면 int로 캐스팅하고 있다.

int형을 받은 경우 메소드를 보면 수많은 분기로 나누고 있는데...각각의 상수가 정의되어 있다.

 

먼저 제일 아래 부분에 getType()이라는 메소드를 봐야하는데,

Charater.getType() 메소드는 파라미터로 char 값을 받으면 특정 값을 반환해준다.

예를 들어 영문 대문자이면 1을 반환, 한글은 5를 반환, 숫자는 9를 반환하는 식이다.

 

그리고 >> 라는 연산자는 오른쪽 시프트 연산자로 비트마스크를 오른쪽으로 이동하는 연산자다.(이런게 있는지 처음봤다.)

10진수를 2진수로 변환해서 비트를 오른쪽으로 한 번 이동시키는 것인데 이를 통해 값을 판별한다.

 

비트마스크를 이동시키는 연산은 더 작은 메모리와 수행시간을 가진다고 한다.

 

그래서 위 코드를 돌려보면 런타임이 2ms 이고, 메모리도 41.7mb로

기존 코드가 런타임 10ms, 메모리 46.5mb인 것에 비해 확연히 줄어든 것을 볼 수 있다.

 

물론 공간복잡도는 배열을 선언하지 않아서 O(n)에서 O(1)로 바뀐 것이 가장 큰 이유겠지만 말이다.

 

정리

String을 판별할때 charAt을 직접 이용하면 배열을 만들지 않아 공간복잡도가 줄어든다.

투포인터를 이용할 때는 꼭 두 개의 이동 조건을 고려하고..까먹지 말 것.

조금만 깊게 들어가도 CS지식이 필요하다는 느낌이 들어 네이버 부스트코스에 CS50을 수강하기 시작했다.