[백준] 1213 팰린드롬 만들기 Node.js (Greedy)

문제

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

예제 입력 1

AABB

예제 출력 1

ABBA

예제 입력 2

AAABB

예제 출력 2

ABABA

예제 입력 3

ABACABA

예제 출력 3

AABCBAA

예제 입력 4

ABCD

예제 출력 4

I'm Sorry Hansoo

---

문제풀이

💡 문제풀이 과정

• 팰린드롬(palindrome) 또는 회문은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등을 말한다.
• 팰린드롬의 조건은 문자열 중 개수가 홀수인 문자의 개수가 하나이거나, 모든 문자 각각의 개수가 짝수 개여야 한다.
  • 예시)
    • AAABB ⇒ 홀수 개인 문자는 A 하나뿐 이므로 가능 ⇒ ABABA
    • ABCC ⇒ 홀수 개인 문자가 A, B 두 개이므로 불가능
    • AABBCC ⇒ 모든 문자가 짝수 개이므로 가능 ⇒ ABCCBA
• 팰린드롬의 구조는 크게 머리, 몸통, 꼬리로 나뉜다. (홀수 개인 문자가 없이 모두 짝수 개로 이루어진 문자라면 몸통은 없을 수도 있다)
• 주어진 문자열을 배열화 후 오름차순 정렬하고 해당 배열을 반복문을 돌면서 shift()하여 첫 번째 부분을 머리(head)의 배열에 push()한다.
• shift()한 요소의 인덱스를 찾을 수 없을 때 (indexOf 값이 -1일 때), 해당 값은 몸통(body)에 넣는다.
• 꼬리(tail) 배열은 머리 배열을 반대로 뒤집은 것과 동일하기에, 꼬리 배열을 깊은 복사하여 reverse()한다.
• 만약 몸통(body)의 길이가 2이상이면 해당 문자열은 팰린드롬을 만들 수 없다.

✅ 답안 #1

const filePath = process.platform == 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('').sort();

const [head, body] = [[], []];
while (input.length) {
  const first = input.shift();
  const idx = input.indexOf(first);
  if (idx === -1) body.push(first);
  else {
    head.push(first);
    input.splice(idx, 1);
  }
}
const tail = [...head].reverse().join('');
if (body.length > 1) console.log("I'm Sorry Hansoo");
else console.log(head.join('') + body.join('') + tail);