[LeetCode 125] valid palindrome (코드, 느낀 점)

• 문제 설명
• 진행 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 Leet Code 125번 문제로

 

"A man, a plan, a canal: Panama"와 같이 문장을 반으로 갈랐을 때 좌우가 대칭되어있는 문장을 판별한다.

ex) 토마토, race a car

 

 

기본적인 palindrome 문제와는 달리

125번은 알파벳이나 숫자 외의 문자가 문장에 포함되었을 경우 이를 무시하고 진행한다.

(이 문제는 대소문자를 동일시한다.)

 

 

 

 

 

진행 과정

 

 

 

내가 문제를 해결하면서 설계한 진행과정이다.

 

알파벳만을 구분하는 함수와 숫자(아스키코드 상 문자)를 구분하는 함수 정의한다.

 

palindrome 문제는 특성 상 문장의 길이가 홀수인 경우 문장의 가운데 문자가 대칭의 기준이 되고

 

 

짝수인 경우에는 다음 그림과 같이 기준이 잡힌다.

그렇기에 전체적인 반복의 횟수는 문장의 좌 우 양 끝에서부터 가운데로 문자를 비교한다 하였을 때

홀수의 경우 대칭의 기준이 되는 문자까지 비교를 , 위 이미지를 예로 '마'

짝수의 경우 기준의 양 옆 문자 까지 비교를 완료하면 판별이 가능하다.

이 두 조건을 만족할 수 있는 경우는 양 끝에 있던 비교인덱스가 교차되었을 때까지다.

 

양 끝 비교인덱스의 진행 방향은 대칭기준

양 끝의 비교인덱스가 교차되었다.

 

반복의 횟수는 정해졌고 

palindrome에 어긋나는 문장임을 증명할 수 있게 

palindrome에 어긋나는 경우를 정의하여 보자.

 

우선적으로는 비교중인 두 문자가 서로 다를 때이다.

하지만 더 깊이 생각해보면 이 문제는 대소문자를 동일시 하기에

ASCII 코드 상 대소문자가 구별되며 그렇기에

이 문제에서는 같다고 여겨질 문자들이 서로 다르다고 판정된다.

 

그렇기에 비교중인 두 문자가 서로 다르며 비교중인 두 문자가

알파벳일 경우 두 문자 중 한 문자에게만 대문자화와 소문자화를 시킨 이후

비교하여 한 번의 일치도 발생하지 않을 경우 틀리다는 것을 반환하게 한다.

(한 문제에게만 대문자화 소문자화를 시키는 이유는

알파벳에서 애초에 이러한 문자간의 틀림이 발생한 이유가

하나는 대문자이고 다른 하나는 소문자이기 때문이다.)

 

그리고 이러한 조건에 해당되지 않는다면 양 끝에서부터 가운데로

하나씩 하나씩 비교해가며 비교인덱스를 옮겨준다.

 

여기까지가 전체적인 문제해결의 과정이다.

 

 

 

코드 전문

 

 

class Solution {
public:
    bool isAlphabet(string& s, int& num)
    {
        if ((s[num] < 'A' || s[num] > 'z') || (s[num] > 'Z' && s[num] < 'a')) return false;
        return true;
    }

    bool isNum(string& s, int& num)
    {
        if (s[num] < '0' || s[num] > '9') return false;
        return true;
    }
    
    bool isPalindrome(string s) {
        int LIdx = 0;
        int RIdx = s.size() - 1;
        
        while (LIdx <= RIdx)
        {
            if (!isAlphabet(s, LIdx) && !isNum(s, LIdx)) LIdx++;
            else if (!isAlphabet(s, RIdx) && !isNum(s, RIdx)) RIdx--;
            else
            {   
                if (s[LIdx] != s[RIdx])
                {
                    if (isAlphabet(s, LIdx) && isAlphabet(s, RIdx))
                    {
                        if (tolower(s[LIdx]) != s[RIdx] &&
                            toupper(s[LIdx]) != s[RIdx]) return false;
                    }
                    else return false;
                }
                LIdx++;
                RIdx--;
                
            }
        }
        return true;
    }
};

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

 

아직 PS쪽은 초초초입문자 단계이지만 특히 문자열 문제에 약한거 같아 

사소한 문제에도 진중하고 깊게 접근하고 싶었습니다. (여기서 사소한 문제라 한 이유는

저한텐 이 문제도 15번의 시도가 필요했고 몇 시간의 시간이 소요되었지만

LeetCode에서는 묵묵히 난이도가 easy임을 고수하였기 때문입니다.

 

이번 문제를 해결하며 접했던 오류에는 알파벳과 숫자를 구별하는 함수를 작성하는 데 있어

비교연산자와 논리연산자, if 조건문 등을 통해 범위를 정하는데 있어 조금 혼동을 느낀 것이 하나입니다.

처음에는 알파벳과 숫자를 하나의 함수에서 구별하고자 계획했는데 단일책임의 문제도 있고

둘을 구분하는게 본문에서도 확장성있게 사용될 것 같아 그렇게 하였습니다.

머리속에서 교집합을 형상시켜 풀려하는데 아직은 어색합니다.

 

사실은 이 글을 적으면서도 코드전문을 여러번 수정하였습니다.

대소문자화는 32를 더하고 빼면서(대문자와 소문자 사이의 간격입니다) 수행하였고

tolower, toupper같은 함수를 알아와 사용하였습니다.

isAlphabet 함수도 if문 하나에 모든 조건을 넣지 않고 if , elseif로 나눠서 수행하였습니다.

그러다가 이렇게도 될려나 싶어서 시도해보았습니다.

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.