[백준] 1213번: 팰린드롬 만들기 (JavaScript)

 

 

 

 

문제

https://www.acmicpc.net/problem/1213

 

개념

그리디 알고리즘

 

구현 코드(JavaScript)

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

const arr = new Array(26).fill(0);
for (const ch of input) {
  arr[ch.charCodeAt(0) - 65]++;
}

let oddChar = '';
let oddCount = 0;
let left = '';
let right = '';

for (let i = 0; i < 26; i++) {
  if (arr[i] % 2 === 1) {
    oddCount++;
    oddChar = String.fromCharCode(i + 65);
  }
}

let result = '';
if (oddCount > 1) {
  result = "I'm Sorry Hansoo";
} else {
  for (let i = 0; i < 26; i++) {
    let ch = String.fromCharCode(i + 65);
    let cnt = arr[i];
    if (cnt % 2 === 0) {
      left += ch.repeat(cnt / 2);
    }
    if (cnt % 2 === 1) {
      left += ch.repeat((cnt - 1) / 2);
    }
  }

  right = left.split('').reverse().join('');
  result = left + oddChar + right;
}

console.log(result);

 

 

코드 설명

이 문제는 시간 복잡도를 해결하기 위해 팰린드롬을 만드는 방법에 대해 고민을 해야했던 문제였습니다.

먼저 단순히 입력받은 문자열을 모든 가능한 순열로 조합한 후 각각이 팰린드롬인지 확인하기에는 시간복잡도가 매우 오바됩니다.
순열을 생성하는 시간 복잡도가 O(n!)이고, 각 순열마다 팰린드롬 검사를 해야 하므로 총 복잡도는 O(n!⋅n)가 됩니다.

따라서 그리디 알고리즘으로 최적의 선택 방법이 어떤 것인지 생각해야 합니다.

 

 

더 효율적인 접근법 찾기

팰린드롬 문자열이 되려면 문자의 등장 횟수 조건을 먼저 조사해야 합니다.

• 문자 개수가 짝수: 모든 문자의 개수가 짝수라면 팰린드롬이 될 수 있습니다.
  • BCBC -> B, C가 각각 두개이므로 BCCB, CBBC로 만들 수 있음
• 문자 개수가 홀수: 한 개의 문자는 홀수여도 되지만, 나머지는 모두 짝수여야 합니다.
  • ABA -> 홀수 개수인 문자가 B 하나이므로 팰린드롬 성립
  • BACCC -> 홀수 개수인 문자가 2개라서, 팰린드롬을 만들 수 없음

 

코드 동작 과정 설명

팰린드롬 구성

다음과 같은 방식으로 효율적으로 팰린드롬을 만들어봅시다!

1. 짝수 개수인 문자들은 양쪽에 나눠서 배치
   예를 들어 "AABBCC" → "ABC|CBA"
2. 홀수 개수인 문자가 있다면 중앙에 배치
   예를 들어 "AABBC" → "ABCBA" (홀수 개수인 C만 중앙, 짝수들은 똑같이 양쪽에 나눠 배치)

 

1. 문자 빈도 계산

const arr = new Array(26).fill(0);
for (const ch of input) {
  arr[ch.charCodeAt(0) - 65]++; // 해당 문자가 등장할 때마다 해당 값 증가
}

• arr 배열을 만들어 알파벳 A부터 Z까지 각각의 문자 빈도를 계산합니다.
  • arr는 길이가 26인 배열로, 각 문자가 얼마나 등장하는지 세는 데 사용됩니다.
  • ch.charCodeAt(0) - 65는 문자 ch의 ASCII 값에서 65(문자 'A'의 ASCII 값)를 빼서 해당 문자의 배열 인덱스를 찾습니다. 예를 들어, 'A'는 arr[0], 'B'는 arr[1], ... , 'Z'는 arr[25]에 해당합니다.

2. 홀수 개수 문자 확인

let oddChar = '';
let oddCount = 0;
let left = '';
let right = '';

for (let i = 0; i < 26; i++) {
  if (arr[i] % 2 === 1) {
    oddCount++;
    oddChar = String.fromCharCode(i + 65); // 'A'
  }
}

• 홀수 개수인 문자를 찾기 위한 과정
  • oddCount는 홀수 개수 문자가 몇 개인지 세는 변수입니다.
  • oddChar는 홀수 개수인 문자를 저장하는 변수입니다. 팰린드롬에서는 홀수 개수인 문자가 한 개만 존재해야 하므로, 각 알파벳이 홀수 개로 등장한 경우를 확인하고, 해당 알파벳을 oddChar에 저장해둡니다.
  • oddCount++로 홀수 개수인 문자의 개수를 카운팅합니다.

4. 팰린드롬 만들기: 불가능한 경우

let result = '';
if (oddCount > 1) {
  result = "I'm Sorry Hansoo";
}

• 만약 홀수 개수인 문자가 1개 초과라면, 팰린드롬을 만들 수 없기 때문에 "I'm Sorry Hansoo"를 출력합니다.

5. 팰린드롬 만들기: 가능한 경우

else {
  // 짝수 개수 문자는 절반을 나눠서 각각 양쪽에 배치
  for (let i = 0; i < 26; i++) {
    const char = String.fromCharCode(i + 65);
    const count = arr[i];
    // 짝수 개수인 문자는 절반만 저장
    if (count % 2 === 0) {
      left += char.repeat(count / 2);
    }
    // 홀수 개수 문자는 짝수 개수만큼 저장
    if (count % 2 === 1) {
      left += char.repeat((count - 1) / 2);
    }
  }

  right = left.split('').reverse().join(''); // 오른쪽 부분 만들기
  result = left + oddChar + right;
}

• 짝수 개수인 문자는 절반만 저장하고, 홀수 개수인 문자는 맨 가운데에 배치합니다.
  • 짝수 개수 문자 처리: 짝수 개수인 문자는 절반만 왼쪽에 배치됩니다. 예를 들어, "AA"이면 "A"를 left에 넣습니다.
  • 홀수 개수 문자 처리: 홀수 개수인 문자는 맨 중간에 하나만 놓습니다. 예를 들어, "AAA"이면 "AA"는 왼쪽에, "A"는 중간에 배치합니다.
• 그 후 오른쪽 부분은 왼쪽 부분을 반대로 뒤집어서 만듭니다.
  • right = left.split('').reverse().join('');는 left 배열을 반대로 뒤집어서 right로 만듭니다.
• 최종적으로 left, oddChar, right를 이어 붙여서 result를 만듭니다!

 

---