[JavaScript 자바스크립트], [Python 파이썬] 백준 1213번 - 팰린드롬 만들기

2024년 7월 1일

문제 링크 :  백준 1213번 - 팰린드롬 만들기

문제

 

 

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

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

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

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

입력

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

출력

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

 

알고리즘 분류

• 구현
• 그리디 알고리즘
• 문자열

---

 

문제 접근

 

팰린드롬(회문)이란, 어느 문자열을 좌우 대칭으로 뒤집어도 같은 문자열을 의미한다.

 

어떤 문자열이 주어졌을 때, 문자들을 적절히 이동시켜 만들 수 있는 팰린드롬 중 사전순으로 앞서는 것을 출력하면 되는 문제이다.

 

우선, 사전순으로 앞서야 하기 때문에 입력받은 문자열들은 오름차순으로 정렬시켜주고 시작해야 한다.

 

다음은 문자열을 정렬시켜 AAABB 라는 정렬된 문자열을 얻고 난 이후 팰린드롬을 만드는 과정이다.

 

 

각 배열과 변수, 포인터가 의미하는 것은 위와 같다.

 

스택을 2개나 선언한 이유는 맨 뒤에서 설명하겠다.

결론부터 말하면 두 스택을 이용해 최종 팰린드롬 문자열을 완성시킬 것이다.

 

팰린드롬이 존재하려면 모든 문자가 짝을 가지고 있거나, 최소한 하나의 문자만 짝이 없어야 한다.(짝이 없는 문자가 하나뿐이면 팰린드롬의 가운데에 위치시키면 된다.)

 

 

현재 비교중인 문자가 없으므로 stack_1에 A를 push 한다.

해당 문자가 짝이 있는지 비교해야 하므로 isComparing을 true로 치환한다.

 

 

isComparing이 true일 때, 즉 문자가 짝이 있는지 비교하고 있는 상태일 때 비교 대상은 stack_1의 가장 마지막 인덱스 문자이다.

 

현재 탐색 중인 문자와 비교하는 문자인 stack_1의 마지막 인덱스 문자가 같으므로 둘은 짝을 이룬다.

 

짝을 이루는데 성공하면 해당 짝은 stack_2에 push 한다.

 

 

현재 비교중이지 않으므로 stack_1에 A를 push 한다.

 

해당 문자가 짝이 있는지 비교해야 하므로 isComparing을 true로 치환한다.

 

 

현재 비교중인 문자는 A인데, 탐색된 문자는 B 이다. 그렇다면 현재 비교중인 문자는 짝이 없다는 의미이다.

 

짝이 없는 문자는 팰린드롬의 중앙에 위치할 수 있으므로, stack_1의 마지막 문자를 pop 해주고, 해당 문자를 center 변수에 대입해 놓는다.

 

이제부터 짝이 없는 문자가 더 등장하면 해당 문자는 절대 팰린드롬이 될 수 없다.

 

 

 

현재 비교중인 문자를 B로 바꾸어주기 위해 stack_1에 push 한다.

 

 

현재 비교중인 문자와 탐색된 문자가 같으므로 둘은 짝을 이룬다.

 

현재 비교하는 문자의 짝을 stack_2에 push 한다.

 

더 이상 탐색할 문자가 없으므로 로직을 종료한다.

 

 

정말 다행이도 짝을 이루지 못하는 문자가 하나 뿐이었다.

 

이 문자열은 팰린드롬이 될 수 있으므로 이제 팰린드롬을 완성시켜보자.

 

 

stack_1에 요소들을 하나 씩 push하여 최종 팰린드롬을 완성시킬 것이다.

 

 

center이 담고 있는 문자는 팰린드롬의 중앙에 위치해야 하므로, 먼저 stack_1에 push 한다.

 

 

stack_2의 마지막 요소를 pop 하여 해당 문자를 stack_1에 append 해준다. 이 과정을 stack_2이 빌 때까지 반복한다.

 

 

 

 

로직이 종료되면 stack_1에 팰린드롬이 완성된다.

 

해당 팰린드롬을 출력하면 문제가 원하는 답을 얻어냈다고 할 수 있겠다.

---

입력 예제

 

AABB
ABACABA
ABCD

 

 

 

출력 예제

 

ABBA
AABCBAA
I'm Sorry Hansoo

 

 

---

전체 코드

 

JavaScript

// 1213

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

function solution() {
    const arr = input.split('').sort();

    var now_idx = 0;
    // 현재 어떤 문자를 확보했고, 다음 문자와 같은지 확인하고싶은 상태
    var isComparing = false;
    var center = "";

    var stack_1 = [];
    var stack_2 = [];

    while (now_idx < arr.length) {
        // 현재 비교하려는 문자가 없는 상태에서 그 다음 문자를 탐색
        // 일단 stack_1에 담아둠
        if (!isComparing) {
            stack_1.push(arr[now_idx]);
            isComparing = true;
        }
        // 현재 비교하려는 문자가 있는 상태에서 그 다음 문자를 탐색
        else {
            // stack_1에 마지막으로 push 된 문자와 같은지 비교. 같으면 그 둘이 한 쌍이 되면 됨.
            if (stack_1[stack_1.length - 1] === arr[now_idx]) {
                stack_2.push(arr[now_idx]);
                // 비교가 끝났으니 false로 다시 바꿔줌.
                isComparing = false;
            }
            else {
                // 하나 쯤은 짝을 이루지 못해도 됨. 팰린드롬 정 가운데에 위치하면 되니까.
                if (center === "") {
                    // 정 가운데에 위치하게 해야하니 일단 stack_1에서 pop 시킴.
                    center = stack_1.pop();
                    // 현재 탐색하는 문자를 stack_1에 push 하고 해당 문자를 기준으로 비교를 시작
                    stack_1.push(arr[now_idx]);
                }
                // 이미 짝을 못 이루는 문자가 존재하는데 또 그런 문자가 존재하면 절대 팰린드롬이 될 수 없음.
                else {
                    return "I'm Sorry Hansoo"
                }
            }

        }

        now_idx += 1;
    }

    // 탐색을 다 완료하였는데, 짝이 없어 팰린드롬 가운데로 와야 하는 문자가 존재할 수 있음.
    if (center !== "") {
        // 그런데 마지막으로 탐색 중인 문자의 짝을 찾지 못했을 경우는 팰린드롬이 될 수 없음
        if (isComparing) {
            return "I'm Sorry Hansoo";
        }
        // 아니라면 팰린드롬 가운데에 위치하도록 함.
        else {
            stack_1.push(center);
        }
    }



    // stack_2를 pop하며 stack_1에 push함.
    // 해당 로직이 끝나고 stack_1에 존재하는 문자를 차례로 출력하면 해당 문자열이 팰린드롬임.
    while (stack_2.length > 0) {
        stack_1.push(stack_2.pop());
    }

    return stack_1.join('');
}

console.log(solution());

 

Python

# 1213

def solution():
    stack_1 = []
    stack_2 = []

    now_idx = 0
    center = ""

    isValid = False
    while now_idx < length:
        if not isValid:
            stack_1.append(name[now_idx])
            isValid = True
        else:
            if stack_1[-1] != name[now_idx]:
                if center == "":
                    center = stack_1.pop()
                    stack_1.append(name[now_idx])
                else:
                    return "I'm Sorry Hansoo"
            else:
                stack_2.append(name[now_idx])
                isValid = False

        now_idx += 1
    
    if center != "":
        if isValid:
            return "I'm Sorry Hansoo"
        else: 
            stack_1.append(center)
    
    while stack_2:
        stack_1.append(stack_2.pop())
    
    return "".join(stack_1)


if __name__ == "__main__":
    name = list(input())
    name.sort()

    length = len(name)

    print(solution())

 

---

풀이 후기

 

조건을 많이 걸어주어야 하는 까다로운 문제라고 생각한다.

 

항상 팰린드롬 문제에서는 스택을 2개 활용해 푸는 방식이 유용하다고 생각한다.