$n^2$ 배열 자르기

공부하며 느낀 점

$n^2$ 배열 자르기

아니 뭔놈의 문제가 이래 복잡해...

왼쪽위부터 오른쪽 아래로 1, 2, 3, 4... 로 채우고
윗줄의 마지막과 아랫줄의 처음을 이어서 하나의 배열로 만들고
left~right로 잘라낸 배열을 출력해내라는 것이다.

나의 풀이

• 1부터 n까지 들어있는 배열을 만든다.
• 그 다음에 그배열의 0~i까지의 요소를 1씩 증가 시킨 배열을 붙이고... ( 최대 i < n 까지 반복)

function solution(n, left, right) {
    let roop = 0
    
    for (roop = 0 ; n*roop <= right ; roop++){}
    
    let row = []
    
    for ( let i = 1 ; i <= n ; i++) {
        row.push(i)
    }
    
    let fullRow = [...row]

    for ( let i = 1 ; i <= roop ; i++) {
        for ( let j = 0 ; j < i ; j++) {
            row[j]++
        }
        fullRow = [...fullRow,...row]
    }
    
    const answer = fullRow.slice(left,right+1)

    return answer
}

내가 생각해도 객체 분해할당을 너무 자주쓰긴했다...

우선 이중 반복문부터 어떻게 처리를 해야한다.

function sol0(n, left, right) {
    let answer = []
    
    for (let i = left ; i <= right ; i++) {
        const share = parseInt(i/n)
        const remainder = i%n
        
        if (share <= remainder) {
            answer.push(remainder+1)
        } else {
            answer.push(share+1)
        }
        
    }
  

    return answer
}

• 배열을 자꾸 복사하고 하나하나 수정하는 것이 아니라, 나누기를 이용해서 몫에 1을 더한 값 또는

처음하고 완전히 달라진것 같지만 더 좋은 결과물이 나왔으니 만족한다.

다른 사람의 풀이

function sol1(n, left, right) {
    var answer = [];

    for (let i = left; i <= right; i++) {
        answer.push(Math.max(i % n, parseInt(i / n)) + 1)
    }

    return answer;
}

• 내가 if문으로 만든 것을 이사람은 Math.max 로 구현했다.

const sol2 = (x,y,z) => Array.from({length:z-y+1},(_,index)=>(index+y)%x<parseInt((index+y)/x)+1?parseInt((index+y)/x)+1:(index+y)%x+1)

역시 화살표 함수로 한줄로 구현했다.

속도 비교

시간 복잡도

모두 $O(n)$의 복잡도를 가진다.

최악의 경우를 보기 위해 의도적으로 left는 0 right는 n^2으로 설정하였다.

반복 횟수 증가

화살표함수에 삼항연산자를 넣은 것이 너무 압도적으ㅡ로 느렸다.

반복 길이 증가

n의 값이 10배 증가할 시(=처리해야할 양 100배 증가)
sol2가 sol0,1에 비해서 절반만 증가하지만 기본시간이 5.5배가 넘기 때문에 의미가 없다...

시간복잡도상으로는 100배 정도 증가해야하는데 200배가 증가한것을 보면 역시 시간복잡도는 대략적인 것인게 확실해보인다.

공부하며 느낀 점

1. 당장 머릿속에 떠오르는 방법을 코드로 옮기는 것도 좋지만, 그것보다 좀더 효율적인 방법을 생각하는 것도 중요하다.
2. 다시 느끼지만 시간복잡도는 절대적인 기준이 아니다.