LeetCode / Greedy / 409번 / Longest Palindrome / JS

< 문제 바로가기 >

Longest Palindrome - LeetCode

 

< 문제 간단설명 >

주어진 문자열의 문자들로 만들 수 있는 문자열 중 가장 긴 팰린드롬 문자열을 만들었을 때 그 길이가 몇인지 반환하면 되는 문제이다.

 

* 펠린드롬: 앞으로 해도 거꾸로 해도 같은 문자열

 

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
    if(s.length === 1) return 1;

    const TOTAL_ALPHABET_COUNT = 'z'.charCodeAt(0) - 'A'.charCodeAt(0) + 1;
    let alphabetCountList = Array.from({ length: TOTAL_ALPHABET_COUNT }, () => 0);

    let alphabetIndex = 0;
    s.split('').forEach((alphabet) => {
        alphabetIndex = alphabet.charCodeAt(0) - 'A'.charCodeAt(0);
        alphabetCountList[alphabetIndex] += 1;
    });

    let oddCount = alphabetCountList.filter((count) => count % 2 === 1);
    let evenCount = alphabetCountList.filter((count) => count % 2 === 0);

    let result = 0;
    result += oddCount.length ? oddCount.reduce((acc, cur) => acc + (cur - 1), 1) : 0;
    result += evenCount.reduce((acc, cur) => acc + cur);

    return result;
};

---

 

- 아스키코드표

번호	코드	번호	코드	번호	코드
33	!	64	@	95	_
34	"	65	A	96	`
35	#	66	B	97	a
36	$	67	C	98	b
37	%	68	D	99	c
38	&	69	E	100	d
39	'	70	F	101	e
40	(	71	G	102	f
41	)	72	H	103	g
42	*	73	I	104	h
43	+	74	J	105	i
44	,	75	K	106	j
45	-	76	L	107	k
46	.	77	M	108	l
47	/	78	N	109	m
48	0	79	O	110	n
49	1	80	P	111	o
50	2	81	Q	112	p
51	3	82	R	113	q
52	4	83	S	114	r
53	5	84	T	115	s
54	6	85	U	116	t
55	7	86	V	117	u
56	8	87	W	118	v
57	9	88	X	119	w
58	:	89	Y	120	x
59	;	90	Z	121	y
60	<	91	[	122	z
61	=	92	\	123	{
62	>	93	]	124	|
63	?	94	^	125	}

 

아스키코드표에서 A~z 까지의 길이만큼 배열을 선언해주고 0으로 초기화를 해주었다.

그리고 input으로 들어온 문자열을 순회하면서 A라면 0, B라면 1, C라면 2, ... 이런식으로 아스키코드표 에서의 순서대로의 인덱스에 각 문자가 나올 때마다 +1 씩 해주었다.

한마디로 인덱스는 알파벳순서이고, 그 인덱스의 값은 알파벳이 몇번 나왔는지의 count 이다.

 

그 후에 홀수개와 짝수개를 값으로 가지는 배열로 filter를 이용해 각각 나눈다.

 

팰린드롬에서는 홀수개의 문자는 단 한번만 나올 수 있다. 왜냐면 팰린드롬 문자열은 좌우대칭을 이루어야 하기 때문에 홀수개의 문자는 중간을 기준으로 대칭을 이루는 형태로 단 한번만 올 수 있다.

따라서 제일 긴 문자열을 만드려면 홀수개중에 제일 많은 홀수개만 올 수 있다.

홀수개를 가지는 나머지 문자들은 모두 사용할 수 없고 하나를 덜 사용해서 짝수개만 이용하면 중간을 기준으로 반반씩 좌,우에 넣으면 되기 때문에 대칭을 이룰 수 있다.

 

홀수개 중에 홀수는 가장 큰 홀수개인 개수만 결과값에 더할 수 있다. 나머지의 홀수들은 딱 한개만 덜 사용해서 짝수개만큼 사용할 수 있다.

예시로 [1, 3, 5, 7, 9] 가 있다면 가장 큰 홀수인 9만 결과값에 더할 수 있다. 홀수개의 문자를 모두 사용하려면 중간을 기준으로 대칭을 이루어야 하기 때문이다.

나머지 홀수들은 하나씩 덜 써서 짝수개를 좌우대칭으로 사용할 수 있다.

따라서 위의 예시로는 9만 온전히 사용가능하고 나머지는 -1씩 된 값을 사용해야 하므로,

[0, 2, 4, 6, 9] 만큼 사용할 수 있다. 가장 큰 값만 1을 빼주지 않기 때문에 모든 값에 대해서 1을 빼준 값을 모두 더한후에 나중에 1을 더해주면 똑같은 값을 얻을 수 있다.

 

짝수개는 반반씩 좌,우에 넣어서 모두 사용할 수 있기 때문에 짝수개가 있는 문자들은 그 개수를 모두 결과값에 더해주면 된다.