[node.js,백준]11054 - 가장 긴 바이토닉 부분 수열

목차

 문제

링크

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

주저리

더 간단하게 풀수있었던거같은데 일단 잘모르겠어서 해결을 해보는 위주로 하였다.

바이토닉 부분 수열은 증가만 하거나 감소만해도 가능하고 증가하다가 감소하는게 바이토닉 핵심이다.

testF함수는 증가하는함수이고 arrs에 길이 저장

testF2함수는 배열을 reverse()해서 똑같이 증가하는함수(=감소하는함수)를 구해준다.

arrsLow에 길이 저장

testF2는 배열을 뒤집은상태에서 증가하는것을 얻은거기때문에 한번더 reverse를 진행해주고

각 인덱스에맞춰서 더해준다.

-1을해주는이유는 자기자신이 포함이되기때문에 겹치는수를 한번 제거해주는 것이다.

그 합을 구해주고 max값을 보내주면 원하는 제출이 된다.

 

풀이

 입력 데이터 처리

• 파일 시스템 모듈(fs)을 사용해 입력을 받습니다. 주석 처리된 부분은 실제 실행 환경에서 사용되며, 테스트를 위해 input 변수에 직접 데이터를 할당합니다.
• 입력 데이터는 줄 바꿈(\n)으로 구분되며, 숫자 배열은 공백으로 분리됩니다.

 동적 프로그래밍 배열 초기화

• arrs 배열은 각 인덱스에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 저장합니다.
• arrsLow 배열은 각 인덱스에서 시작하는 가장 긴 감소하는 부분 수열의 길이를 저장합니다.

부분 수열 계산 함수 testF

• 이 함수는 주어진 배열에 대해 각 요소를 순회하면서, 그 요소보다 앞에 있는 모든 요소들 중에서 해당 요소보다 작은 요소들의 arrs 값을 참조하여 가장 긴 증가하는 부분 수열의 길이를 업데이트합니다.

 역방향 부분 수열 계산 함수 testF2

• 이 함수는 배열을 역순으로 처리하여, 각 요소에 대해 그 요소 이후에 있는 모든 요소들 중 해당 요소보다 큰 요소들의 arrsLow 값을 참조하여 가장 긴 감소하는 부분 수열의 길이를 계산합니다.

 최종 계산

• testF와 testF2 함수로 계산된 두 배열 arrs와 arrsLow를 이용해 각 요소에서의 바이토닉 수열 길이를 계산합니다. 이는 두 값의 합에서 1을 빼줌으로써 각 요소가 중복 계산되는 것을 방지합니다.
• 결과 배열 중 최대값을 찾아 출력함으로써 가장 긴 바이토닉 부분 수열의 길이를 도출합니다.

 코드

// 가장 긴 증가하는 부분 수열
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

let real = input.trim().split("\n");
let arrs = [];
let arrsLow = [];

function testF(N, rest) {
    // for (let i = 0; i < 1; i++) arrs[0][i] = 1;

    for (let i = 0; i < N; i++) {
        // let reArr = [];
        if (i === 0) {
            arrs[i] = 1
        }
        else {
            arrs[i] = 1;
            let sliced = rest.slice(0, i);
            let filtered = [];
            for (let j = 0; j < sliced.length; j++) {
                let r = sliced[j];
                // console.log(rest[i], r, rest.slice(0, i));
                if (rest[i] > r) {
                    filtered.push(arrs[j]);
                }
            }
            if (filtered.length > 0) {
                arrs[i] = Math.max(...filtered) + 1
            }

        }
        // arrs.push(reArr);
    }
}

function testF2(N, rest) {
    // for (let i = 0; i < 1; i++) arrs[0][i] = 1;
    let newRest = rest.reverse();
    for (let i = 0; i < N; i++) {
        // let reArr = [];
        if (i === 0) {
            arrsLow[i] = 1
        }
        else {
            arrsLow[i] = 1;

            let sliced = newRest.slice(0, i);
            // console.log({ i, sliced, newRest });
            let filtered = [];
            for (let j = 0; j < sliced.length; j++) {
                let r = sliced[j];
                // console.log(rest[i], r, arrsLow);
                if (rest[i] > r) {
                    filtered.push(arrsLow[j]);
                }
            }
            // console.log({ filtered })
            if (filtered.length > 0) {
                arrsLow[i] = Math.max(...filtered) + 1
            }

        }
        // arrs.push(reArr);
    }
}

function solution(real) {
    let [T, sec] = real;

    let rest = sec.split(" ").map(Number);
    if (Number(T) === 1) {
        console.log(sec[0]);
        return;
    }
    testF(Number(T), rest)
    testF2(Number(T), rest)

    let reArrL = arrsLow.reverse();

    const result = arrs.map((value, index) => value + reArrL[index] - 1);
    // console.log(arrs)
    // console.log(arrsLow)
    // console.log(result);
    console.log(Math.max(...result))
}
solution(real);