[백준] 짝수펠린드롬 (Node.js)

06/06 Node.js로 푼사람이 없어서 작성.

 

문제 - https://www.acmicpc.net/problem/21925

21925번: 짝수 팰린드롬

 

- 이 문제의 요점을 확인해보면

1. 부분 수열을 최대로 합니다.

   앞쪽부터 확인하여 펠린드롬이 만들어지면 갯수를 추가하면됩니다.

 

2. 모든 부분수열은 무조건 짝수 펠린드롬입니다.

   [1, 2, 1, 3, 2, 3]은 [1, 2, 1], [3, 2, 3]으로 펠린드롬을 만들수 있지만

   각 부분 수열의 갯수가 3개이므로 짝수 펠린드롬이 아닙니다.

 

3. 배열의 모든 값을 사용합니다.

   [1, 6, 5, 5, 6, 7]와 같은 경우 : 가운데 중간에 [6, 5, 5, 6]이 있음에도 1과 7 때문에 펠린드롬수가 되지 않습니다. 

 

3. 펠린드롬 수로 대응되는 숫자는 항상 같습니다.

   [11, 1], [2, 22]와 같은 형태의 수열은 짝수 펠린드롬이 아닙니다.   

 

- 답안 (참고용)

const solution = (arr) => {
    let answer = 0;
    //수열원소의 갯수
    const n = arr[0];
    const _arr = arr[1].split(" ");
    //짝수 펠린드롬의 왼쪽 절반에 해당되는 배열
    let dp = [];
    
    for(let i = 0; i < n; i++) {
    	//n보다 많으면 오른쪽 절반을 만들 수 없음
        if(dp.length + i > n) {
            console.log(-1);
            return;
        }
        //조회 값과 dp의 마지막값이 같으면 펠린드롬이 나올수 있는 최소구간
        if(dp[dp.length-1] === _arr[i]) {
            //각 대응되는 숫자 확인
            let check = true;
            for(let j = 0; j < dp.length; j++) {
               if(dp[j] !== _arr[(dp.length-1-j) + i]){
                  check = false;
                  break;
               }
            }
            //펠린드롬 완성
            if(check) {
            	//오른쪽 절반은 확인 불필요
                i += dp.length - 1; //for문이 끝나면 i++ 되므로 -1
                dp = []; //초기화
                answer++;
                continue; //현재 값을 push할 필요 없음.
            }
        }
        //바로 이전값과 다르거나 펠린드롬이 안만들어지면 추가.
        dp.push(_arr[i]);
    }
    console.log(answer);
}

const rl = require('readline').createInterface({input : process.stdin});

const lines = []

rl.on('line', (l) => {
    lines.push(l)
}).on('close', () => {
    solution(lines);
    process.exit();
})