[백준 14002번 가장 긴 증가하는 부분 수열 4 - node.js] [알고리즘 기초 1/2]

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

14002번: 가장 긴 증가하는 부분 수열 4

 

문제

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

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

 

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

예제 입출력

 

입력	출력
6 10 20 10 30 20 50	4 10 20 30 50

 

풀이[node.js]

 

 

728x90

이번 문제는 앞의 문제에서 index만 구해오면 되는 문제이다.

앞에서 max값을 구할 때에, 해당 max값의 index를 maxIndex에 넣어준다.

하지만, 만약 max값을 구하지 못할 때에는 maxIndex 또한 지정되면 안된다.

예를 들어 maxIndex를 max와 같이 초기에 0으로 설정을 해주면 무조건 maxIndex는 0이 되어 최대값의 index가 0이되버리므로, maxIndex는 -1로 지정해준다.

만약, maxIndex가 -1이라면, inputs[i]값이 이전의 값들보다 작은 경우가 아니므로, 해당 인덱스의 arr값은 해당 인덱스의 값만 넣어주고, maxIndex가 -1이 아닌 다른 값이 지정되었다면, max값을 갖고 있는 arr의 값을 가져와서 본인 인덱스의 값을 붙여줘서 arr[i]값을 완성하면 된다.

 

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(inputs[0]);
var inputs = inputs[1].split(' ').map(v=>Number(v));
var dp = new Array(cases).fill(0);
var arr = [];
for(var i=0; i<cases; i++){
    var max = 0;
    var maxIndex = -1;
    for(var j=0; j<i; j++){
        if(inputs[i] > inputs[j] && dp[j] > max){
            max = dp[j];
            maxIndex = j;
        }
    }
    dp[i] = max + 1;
	arr[i] = maxIndex !== -1 ? arr[maxIndex].concat(inputs[i]) : [inputs[i]];
}
var maxLength = Math.max(...dp);
console.log(maxLength);
console.log(arr[dp.indexOf(maxLength)].join(' '));