[알고리즘] Leetcode Longest Palindrome

 

1. 개요

문자열이 주어졌을 때 문자열에서 만들어낼 수 있는 최대 회문 문자열을 구한 뒤 그 길이를 리턴하는 문제이다

Longest Palindrome - LeetCode

 

2. 풀이

처음엔 문제 접근을 잘못해서 원본 문자열 순서 그대로 문자를 유지하면서 만들어야하는 줄 알았다. 그런데 그게 아니라 주어진 문자열의 문자들을 사용하여 만들 수 있는 최대 회문 문자열 길이를 구하는게 정답이었다.

 

따라서 다시 풀어보면 s라는 문자열의 문자 하나하나를 해쉬 키로 만든다. 이후 같은 문자라면 해쉬에서 값을 증가시켜준다

전체 문자열에 대한 해쉬맵을 만들었다면 해쉬키로 순회하며 문자에서 전체 짝수들을 더한다. 홀수라면 하나를 빼서 짝수값으로 더해주고 홀수 문자열은 회문에서 하나 들어갈 수 있으니 홀수로 만들어진게 있다면 최대 회문 문자열에서 하나 더 해주면 된다

 

/**
 * @param {string} s
 * @return {number}
 *
 * 가장 긴 회문 문자열의 길이를 반환하기
 *
 * 현재 문자열을 파싱해서 만드는게 아니라 문자열 자체를 만들어야한다.
 *
 * 대소문자 구분
 */
var longestPalindrome = function (s) {
  const map = new Map();
  const maxArr = [];

  let answer = 0;

  for (const char of s) {
    if (map.has(char)) map.set(char, map.get(char) + 1);
    else map.set(char, 1);
  }

  console.log(map);

  for (const [char, value] of [...map]) {
    if (value % 2 === 0) answer += value; //짝수는 더한다
    else {
      answer += value - 1;
      maxArr.push(char);
    } // 홀수는 짝수로 만들어 더한다
  }

  return answer + (maxArr.length > 0 ? 1 : 0);
};

console.log(
  longestPalindrome(
    "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"
  )
);JAVASCRIPT