프로그래머스 > 월간 코드 챌린지 시즌3 > N^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

[1차 시도]

function solution(n,left,right){
  let answer=[]
  for(let i=0;i<n;i++){
    let temp = i+1
    answer = answer.concat(Array(temp).fill(temp));
    temp++
    for(let j=temp;j<n+1;j++){
     answer.push(Number(j))
    }
  }
   let newArr=answer.slice(left,right+1)
  return newArr
}

시간 초과로 인해 몇몇개의 테스트코드를 통과하지 못한 첫번째 시도의 코드이다.

이중 for 문으로 인해 시간 복잡도 O(n^2)를 가지고 있다.

단순하게 생각해봐도 최종적으로 내보내는 배열의 길이는 right-left+1 만큼의 배열인데,

이를 구하기 위해 n^2 만큼의 길이의 배열을 전부 저장하고 있다가 마지막에서야 slice()를 통해 배열의 일부분만을 리턴하는 코드라서 굉장히 비효율적임을 생각해볼 수 있다.(그래서 어떻게 해야하는데....)

 

[2차 시도]

 

const solution = (n,left,right) =>{
  let answer=[]
for(i=left;i<right+1;i++){
  const rowNum= parseInt(i/n)+1; // 현재 행의 number
  const colNum= i%n +1 // 현재 열의 number
  answer.push(Math.max(rowNum,colNum))
  
}
return answer
}

2차 시도에는 처음부터 딱 right-left+1 만큼의 배열을 만들어

어떠한 left, right, n간의 규칙성을 찾아 딱 그 길이 만큼의 배열을 만들자가 목표가 되었다.

꽤 오랜시간 고민을 한 끝에 위의 코드로 구현에 성공하게 되었다.

 

rowNum은 n^2 행렬에서 가로줄의 위치(1<=rowNum<=n)을 의미하고,

colNum은  n^2 행렬에서 세로줄의 값(rowNum<=colNum<=n)을 의미한다.

 

answer.push(Math.max(rowNum, colNum)) <=의 경우, n^2의 배열의 특성을 살펴보면

rowNum번째 행의 배열의 최솟값이 rowNum임을 이용하면 된다.

rowNum이 1일 때, colNum은 1<=colNum<=n

rowNum이 2일 떄, colNum은 2<=colNum<=n

.

.

.

즉, Math.max(rowNum,colNum)을 배열에 push 해주면 이차원 배열의 값을 그대로 넣어줄 수 있다.

(이거는 이해가 안되면 실제로 값을 넣어봐서 확인하면 됨)

 

1,2,3,4 // rowNum=1,  colNum=1,2,3,4, Math.max(rowNum,colNum)=1,2,3,4

2,2,3,4 // rowNum=2, colNum=1,2,3,4,Math.max(rowNum,colNum)=2,2,3,4

3,3,3,4 // rowNum=3, colNum =1,2,3,4, Math.max(rowNum,colNum)=3,3,3,4

4,4,4,4, //rowNum=4, colNum=1,2,3,4, Math.max(rowNum,colNum)=4,4,4,4