[JavaScript] 백준 17609 회문 (JS)

회문

📚 문제 설명

단어가 주어졌을 때 그 단어가 앞뒤로 똑같게 만들고 싶다.
예를 들어 apbba 가 있으면 p 를 제거해 abba 라는 단어로 만들고 싶다는 것이다.

만약 한개를 제거하고 만들었으면 1
제거를 안해도 되면 0
1개를 지워도 불가능하면 2를 출력하는 문제이다.

👨🏻‍💻 풀이 과정

처음에는 스택을 이용할까 했는데, 앞뒤로 비교를 하며 나아가야하기 때문에 투 포인터를 이용하기로 했다.
그럼 여기서 문제는 만약 투 포인터로 비교하면서 오다가 값이 다른 것을 만났을 때 어떻게 하는가인데, 여기서 일단 생각나는대로 구현을 해보았다.

• 투 포인터를 이용하여 만약 값이 같다면, Start++, End--
• 값이 서로 다르다면, Start + 1 값과 End - 1 값을 비교.
  • 만약 해당 값이 End 혹은 Start 와 같다면, Start++ 혹은 End-- 진행, flag 값을 변경
  • 만약 해당 값이 End 혹은 Start 와 다르다면, 2를 리턴
• flag 값을 확인후 1 혹은 0을 리턴

첫번째 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let answer = '';
    const CheckPalin = (INPUT) => {
        let Start = 0;
        let End = INPUT.length - 1;
        let flag = false;
        while (Start < End) {
            if (INPUT[Start] === INPUT[End]) {
                Start++;
                End--;
            } else {
              	// 만약 이미 한번 제거를 했는지 확인
                if (!flag) {
                    if (INPUT[Start + 1] === INPUT[End]) {
                        flag = true;
                        Start++;
                    }else if (INPUT[Start] === INPUT[End - 1]) {
                        flag = true;
                        End--;
                    }else return 2;
                }else return 2;
            }
        }
        return flag ? 1 : 0;
    };
    input.forEach(v => {
        answer += `${CheckPalin(v)}\n`;
    });
    console.log(answer);

그런데 이렇게 풀면 틀리게 된다.
그 이유는 바로 나는 투 포인터를 이용해 나아가다가 다른 값을 발견했을 때, 포인터 각각 한단계씩 확인해보고 값이 같으면 그 포인터를 옮겨 주었다.
그렇게 된다면 "abccbca" 이 문자열에서 요류가 발생하게 된다.

그래서 수정한 로직의 과정은 다음과 같다.

• 투 포인터가 나아가다가 서로 다른것을 확인
  • 또 다른 함수를 이용하여 투 포인터로 해당 단어가 앞뒤로 똑같은지 확인, 결과에 따라 1또는 2 리턴
• 0리턴

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let answer = '';
	// 투 포인터를 주면 단어의 앞뒤가 같은지 확인해주는 함수
    const Check = (Word, Start, End) => {
        while (Start < End) {
            if (Word[Start] === Word[End]) {
                Start++;
                End--;
            }else return false;
        }
        return true;
    };
	// 메인 로직 함수
    const CheckPalin = (INPUT) => {
        let Start = 0;
        let End = INPUT.length - 1;
        while (Start < End) {
            if (INPUT[Start] === INPUT[End]) {
                Start++;
                End--;
              // 만약 값이 서로 다르다면
            } else {
              	// Check 함수로 하나씩 확인
                if (Check(INPUT, Start + 1, End) || Check(INPUT, Start, End - 1)) {
                    return 1;
                }else return 2;
            }
        }
        return 0;
    };

    input.forEach(v => {
        answer += `${CheckPalin(v)}\n`;
    });
    console.log(answer);

🧐 후기

투 포인터를 사용한다는 것까지는 알았는데 한번 틀리고 나서 다른 풀이가 생각이 도저히 안 나서 결국 다른 분의 풀이를 보고 다시 풀었다. 아직 투 포인터를 이용하는 문제에 몸에 덜 체득된 것 같다.