문제 정의
문자열 하나를 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수는 문자열의 각 문자에 대해 다음과 같은 규칙으로 연산을 수행할 수 있습니다.
- 모든 문자는 반드시 알파벳상 바로 앞 또는 바로 뒤에 있는 문자로 변경해야 합니다.
- 단, "a"는 "b"로만, "z"는 "y"로만 변경할 수 있습니다. (알파벳 범위를 벗어날 수 없기 때문입니다.)
함수는 이러한 변경을 적용한 결과 중 적어도 하나라도 회문(palindrome)이 될 수 있다면 true를 반환하고, 어떻게 변경해도 회문이 될 수 없다면 false를 반환해야 합니다.
핵심 아이디어
회문인지 판단하려면 문자열의 앞쪽 문자와 뒤쪽 문자를 짝지어 비교해야 합니다. 여기서 중요한 점은 두 문자가 서로 인접한 알파벳 관계여야 한다는 것입니다.
- 두 문자가 완전히 같은 경우(거리 0): 둘 다 같은 방향으로 한 번씩 변경하면 여전히 서로 같아지므로 회문이 가능합니다.
- 두 문자가 정확히 2만큼 떨어진 경우(예: "a"와 "c"): 가운데 문자인 "b"로 각각 한 칸씩 이동하면 같은 문자가 되므로 회문이 가능합니다.
- 두 문자가 1만큼 떨어진 경우(예: "a"와 "b") 또는 3 이상 떨어진 경우: 어떻게 변경해도 서로 같은 문자로 만들 수 없으므로 회문이 불가능합니다.
즉, 대응되는 두 문자의 문자 코드 차이가 1이거나 2보다 크면 즉시 false를 반환하면 됩니다.
예제 코드
다음은 위 로직을 구현한 코드입니다.
const str = 'adfa';
const canFormPalindrome = (str = '') => {
const middle = str.length / 2;
for(let i = 0; i < middle; i++){
const first = str[i].charCodeAt()
const last = str[str.length - (i + 1)].charCodeAt()
const distance = Math.abs(last - first)
if(distance > 2 || distance === 1){
return false;
};
};
return true;
};
console.log(canFormPalindrome(str));
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
true
동작 과정 살펴보기
입력 문자열이 'adfa'일 때, 길이의 절반(2)만큼 반복하며 양 끝에서부터 문자 쌍을 비교합니다.
- 첫 번째 비교: "a"(97)와 "a"(97) → 거리 0 → 통과
- 두 번째 비교: "d"(100)와 "f"(102) → 거리 2 → 둘 다 "e"로 변경 가능 → 통과
모든 쌍이 조건을 만족하므로 최종적으로 true가 반환됩니다. 실제로 "d"를 "e"로, "f"를 "e"로 변경하면 "aeea"라는 회문을 만들 수 있습니다.
마무리
이 문제의 핵심은 문자를 실제로 변경해 보면서 모든 조합을 검사하는 것이 아니라, 양 끝 문자 쌍의 알파벳 거리만 계산하면 되는 것입니다. 이렇게 하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다.