[Leetcode] 409. Longest Palindrome - C++

문제 링크

 

풀이 (CPP)

• 접근 방법
  
  1. 팰린드롬을 이루는데에는 양쪽 끝에 위치할 같은 알파벳이 2개씩 필요함 + 한 가운데에는 알파벳 한개만 넣어도 됨
     • ex) abcba
  2.  팰린드롬은 알파벳으로만 이루어져있으며, 대소문자를 구별한다.
     • -> 아스키코드를 사용해서 카운팅해볼까?
  3. 정리: 아스키코드 A ~ z 의 길이(58)의 배열을 만들어서 주어진 문자열을 돌면서 각 인덱스의 문자가 등장하는 횟수를 저장하자!
     
     • 짝수 번 등장했으면 result의 길이를 2씩 늘려주기 (양쪽 끝)
     • 예제 문장을 한바퀴 다 돌고난 뒤 만약 1번만 나타난 문자가 있다면 result의 길이를 1 늘려주기 (가운데)

 

• 구현 코드

class Solution {
public:
    int longestPalindrome(string s) {
        const int asciiLen = 58;
        int result = 0;
        int charCount[asciiLen];

        for(int i = 0; i < s.length(); i++) {
            int curr = s[i] - 65;
            charCount[curr]++;
            
            if(charCount[curr] == 2) {
                result += 2;
                charCount[curr] = 0;
            }
        }

        for(int i = 0; i < asciiLen; i++) {
            if(charCount[i] == 1) {
               result +=1;
               break;
            }
        }
        return result;
    }
};

 

다른 사람들의 답변을 보니 해시맵이나 해시테이블을 많이 썼던데 아직 나는 이 부분에 대한 이해가 부족해서 한번 직접 구현을 해봐야 알 것 같다. 🥹