백준 14002번: 가장 긴 증가하는 부분 수열 4 - javascript

백준 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

접근

이전에 풀은 부분 증가 수열의 최대길이를 구하는 문제의 추가 버전일뿐이다. 매번 최대 길이 값을 저장하는 배열 외에 최대 길이의 배열을 저장하는 배열을 추가로 만들면 된다.

i = 0 일때

배열 값	10	20	10	30	20	50
최대길이	1	0	0	0	0	0
최대배열	10	-	-	-	-	-

0번째 값보다 작은수는 없으므로 최대 길이는 1이다

i = 1 일때

배열 값	10	20	10	30	20	50
최대길이	1	2	0	0	0	0
최대배열	10	10,20	-	-	-	-

1번쨰까지 배열 중 1번째 값보다 작은 수는 10하나가 있는데 10까지의 최대 부분증가 수열의 길이는 1이므로 1 + 1 = 2가된다.

i = 2 일때

배열 값	10	20	10	30	20	50
최대길이	1	2	1	0	0	0
최대배열	10	10,20	10	-	-	-

2번째까지 배열 중 2번째 값보다 작은 수는 없으므로 i = 2의 최대 부분 증가 수열의 길이는 1이다.

i = 3 일때

배열 값	10	20	10	30	20	50
최대길이	1	2	1	3	0	0
최대배열	10	10,20	10	10,20,30	-	-

3번째까지 배열 중 3번째 값인 30보다 작은 수는 10, 20, 10 전부 해당된다. 이 중에서 20까지의 부분증가 수열 길이인 2가 제일 크기때문에 2 + 1 = 3으로 30까지의 최대 부분 증가 수열의 길이는 3이 된다.

결론

배열 값	10	20	10	30	20	50
최대길이	1	2	1	3	2	4
최대배열	10	10,20	10	10,20,30	10,20	10,20,30,50

위와 같은 방식으로 진행하다보면 20은 최대 2, 마지막 수인 50은 앞서나온 수열 중 최대 길이인 3과 더해서 길이가 4인 부분 증가 수열이 된다.

이렇게 해서 구해진 최대길의 배열의 max 값을 구하고 array.indexOf()를 이용해서 해당 max값의 인덱스값을 구해서 max array값도 같이 반환 해주면된다.

++javascript로 풀때 잘 봐야할 점

나는 이번 문제를 풀 때 맨처음 입력받은 N개의 배열을 이용하여 하나는 reduce함수를 돌리는 용도로 사용했고, 다른 하나는 최대 배열을 저장하는 용도로 사용하려고 했었다. 하지만 그 결과 최대 배열을 저장하기 위해 복사한 배열의 내용이 바뀌면 원본 배열도 변경되어 제대로 풀이가 진행되지 않았다. 우리는 JS의 = 복사가 기본적으로 얕은 복사를 한다는 것을 알아야 한다.

//Primitive type deep copy
var origin = 'A';
var copy = origin;
console.log('copy: ' + copy);  // A
copy = 'B';
console.log('origin: ' + origin); // A
console.log('copy: ' + copy); // B

//Reference type shallow copy
var origin = {a:1};
var copy = origin;
console.log('copy: ' + copy.a); // 1
copy.a = 2;
console.log('origin: ' + origin.a); // 2
console.log('copy: ' + copy.a); // 2

위의 코드처럼 = 을 이용하여 복사를 하게 되면 객체나 참조 타입의 경우 얕은 복사가 일어나는 것을 볼 수 있다.

따라서 우리는 lodash 라이브러리나 JSON.stringify()를 통해서 깊은 복사를 해줘야 할 필요가 있다.

const obj = {
  a: 1,
  b: {
    c: 2,
  },
};

const copiedObj = JSON.parse(JSON.stringify(obj));

copiedObj.b.c = 3

obj.b.c === copiedObj.b.c //false 

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let arr = input[1].split(' ');
  let answer = max_sub_dp(arr);
  console.log(answer);
  process.exit();
});

function max_sub_dp(arr){
  let result_arr = JSON.parse(JSON.stringify(arr));  
  let max_sub = arr.reduce((acc,cur,idx,arry)=>{    
    let tmp = [];
    let index = [];
    for(let i = 0 ; i<idx+1;i++){      
      if(arry[i]<parseInt(cur)){
        tmp.push(acc[i]);
        index.push(i);
      }
    }    
    if(tmp.length>0){
      let max = Math.max(...tmp);
      acc[idx] += max;
      
      let k = index[tmp.indexOf(max)];      
      result_arr[idx] =  result_arr[k]+' '+result_arr[idx];
    } 
    return acc;
  },Array(arr.length).fill(1));     
  return Math.max(...max_sub)+'\n'+result_arr[max_sub.indexOf(Math.max(...max_sub))];
}