LeetCode 125번 문제

문제 링크:
https://leetcode.com/problems/valid-palindrome/

문제는 다음과 같다.

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.

문제 설명

주어진 문장에서 알파벳과 숫자만을 남긴 뒤에, 문장의 앞 뒤 어디에서 시작해서 읽어도 같은 문장이면 Palindrome이 된다.

주어진 문장이 Palindrome이라면 True를, 아니라면 False를 return하면 되는 간단한 문제이다.

솔루션 코드는 세 단계로 나눠서 발전시킬 수 있다.

1번 풀이

def sol(input_string):
    # 새로운 리스트 선언
    strs = []
    for char in input_string:
        # 숫자와 알파벳만을 남긴다 (isalnum)
        if char.isalnum():
            # if문을 통과한 문자에 대해 소문자를 적용한다 (char.lower())
            strs.append(char.lower())

    # strs에 요소가 남아있는 동안 반복문 실행
    while len(strs) > 1:
        # 앞 뒤 문자가 다르다면 False를 return한다
        if strs.pop(0) != strs.pop():
            return False

    return True

1. 먼저 strs라는 새로운 list를 생성한다.
2. for문에서 input_string의 모든 문자를 돌면서 숫자와 알파벳만을 판별한다.
3. if 문에서 isalnum()이라는 함수를 이용해 알파벳 또는 숫자를 판별해낼 수 있으며, 해당 if문에 걸린 요소는 lower()함수를 거쳐 소문자로 변환된 뒤에 strs리스트에 append된다.
4. strs에 요소가 존재한다면 strs 리스트가 남아있는 동안 While문을 이용해 loop를 돌면서 맨 앞의 문자와 맨 뒤의 문자가 다른 지를 판별한다.
   여기서 strs.pop(0)과 strs.pop()을 이용하여 맨 앞과 맨 뒤의 문자를 꺼내오는 것을 확인할 수 있다.
   여기서 pop은 stack에서의 pop과 같은 의미이며, 인자로 0이 들어가게 되면 첫 번째 요소를 반환한다.
5. 4번의 loop과정을 거쳐, 만약 앞뒤가 다른 문자가 발견되지 않았다면 True를 반환하게 된다.

1번 풀이 사용 함수 및 자료형

여기서 알게 되는 몇 가지 함수가 있다.
str.isalnum(), str.lower(), list.pop()

str.isalnum():
str의 문자열이 알파벳과 숫자로만 이루어져 있다면, True를 그 외의 문자가 포함되어있다면 False를 반환한다.
str.lower():
str의 문자열을 소문자로 변환한다.
list.pop():
list의 가장 마지막 요소를 반환하고 삭제한다. 인자로 0이 들어간다면 첫 번째 요소를 반환하고 삭제한다.

2번 풀이

def sol(input_string):
    # 자료형 데크로 선언
    strs: Deque = collections.deque()
    for char in input_string:
        # 숫자와 알파벳만을 남긴다 (isalnum)
        if char.isalnum():
            # if문을 통과한 문자에 대해 소문자를 적용한다 (char.lower())
            strs.append(char.lower())

    # strs에 요소가 남아있는 동안 반복문 실행
    while len(strs) > 1:
        # 앞 뒤 문자가 다르다면 False를 return한다
        if strs.popleft() != strs.pop():
            return False

    return True

2번풀이는 1번풀이에서 발전시킨 형태인데, strs를 list로 선언하지 않고, Deque라는 자료형으로 선언하였다.

1번풀이에서처럼 단순하게 리스트로 처리할 수 있지만, 효율성면에서 Deque는 높은 성능을 보인다. list에서의 pop(0)은 성능이 O(n)인데 반해, deque에서의 popleft()는 O(1)이기 때문이다.

알고리즘을 푸는 것 뿐만 아니라, 실행 속도까지 신경써야하는 코딩테스트에서는 위와같은 발전이 중요할 것이다.

이러한 방법을 통해 1번 문제에서 보다 5배 빠른 코드를 만들 수 있었다.

2번 풀이 사용 함수 및 자료형

Deque:
list 대신 사용할 수 있다.
list에서의 선언이

strs = []

이었다면,
Deque의 선언은 다음과 같다

strs: Deque = collections.deque()

list에서의 strs.pop(0)는 strs.popleft()로 대체되며 코드의 성능이 O(n)에서 O(1)로 향상된다.

3번 풀이

def sol(input_string):
    input_string = input_string.lower()
    # 정규식으로 불필요한 문자 필터링
    input_string = re.sub('[^a-z0-9]', '', input_string)

    return input_string == input_string[::-1] # 슬라이싱

Deque로도 충분하지만 더 빨라질 수 있는 여지가 남아있다.
바로 슬라이싱을 사용하는 방법이다.

1. lower()함수를 사용해 문자열의 모든 대문자를 소문자로 바꾼다.
2. re.sub()의 정규식을 이용하여 알파벳과 숫자가 아닌 문자를 모두 ''(빈 문자열)로 대체한다.
3. input_string[::-1]의 슬라이싱을 사용하여 문자열을 반대로 정렬되도록 바꾸고 기존의 input_string과 비교한다.
4. 비교값이 동일하다면, 즉 문자열이 palindrome이라면 True를 아니라면 False를 반환한다.

1번과 2번 풀이와는 다른 방식을 사용하고, 몇가지 함수를 사용하여 코드를 단순화하였다. 3번의 방법을 통해 2번의 방법에서보다 2배 더 빠른 코드를 만들 수 있다.

3번 풀이 사용 함수 및 자료형

정규식을 이용한 필터링:
re.sub('[^a-z0-9]', '',s)
s문자열의 a-z,0-9 를 포함하지 않는 모든 문자를 공백으로 대체한다.

슬라이싱:
주어진 문자열
0 1 2 3 4
안녕하세요

s[1:4] == '녕하세'
문자열에서 인덱스 1에서 4이전까지를 출력한다.

s[1:-2] == '녕하'
인덱스 1에서 -2(3) 이전까지를 출력한다.

s[:]
문자열의 사본을 return한다.

s[-1] == '요'
문자열의 마지막 문자를 반환한다.

s[-4] == '녕'
뒤에서 4번째(1) 문자열을 반환한다.

s[-3:] == '하세요'
-3(2)위치에서 문자열의 끝까지를 반환한다.

s[::1] == '안녕하세요'
문자열 그대로를 반환한다.

s[::-1] == '요세하녕안'
문자열을 뒤집는다 (3번 풀이에서 사용)

s[::2] == '안하요'
두칸씩 앞으로 가면서 출력한다.