[TIL #10] n^2 배열 자르기

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

프로그래머스

 

풀다 보니 문제가 재밌었다.

처음 봤을 땐, "이게 뭔 소리야?" 싶었지만...

 

다른 사람들을 보니, 이 이미지에 많이 낚인 것 같았다.

`n`이 최대 10^7이었기 때문에 이렇게 풀면 무조건 타임 오버라고 생각했다.

그래도 일단 저 대로 풀어봤다.

정답이 바로 떠오르지 않았기 때문에...

 

function solution(n, left, right) {
    let arr = new Array();
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            arr.push(Math.max(i + 1 , j + 1));
        }
    }
    
    return arr.slice(left, right + 1);
}

어차피 이어 붙이기 때문에 2차원 배열은 만들 필요가 없다.

그대로 1차원 배열에 쭉 추가해 준다.

그리고 ``slice()``로 필요한 영역만 잘라 리턴.

그 결과는....

 

그럼 그렇지. 시간이 엄청 걸릴 것임이 분명했다.

사실 이미지대로 2차원 배열을 만들고 그걸 이어 붙이는 것도 해 보긴 했다.

중간에 하다가 이건 진짜 아닌 거 같아서 위 방법으로 선회한 것.

 

사실 중요한 건, 난 문제를 보고 얼마 지나지 않아 규칙을 파악했다는 것이다.

각 칸에 지정된 값은, 각 X, Y 좌표값을 비교한 후, 그중 큰 값이라는 것.

그래서 ``arr.push(Math.max(i + 1, j + 1))``라는 코드가 나올 수 있었다.

 

for문을 2중이 아닌 하나로 줄여서 일자로 쫙 배열을 만든다.

시작은 ``left``고 끝은 ``right + 1``이면 되겠다.

그럼 버리는 값 없이 필요한 값만 생성하면 최적해라고 볼 수 있다

이는 다음과 같이 구현했다.

 

function solution(n, left, right) {
    let arr = new Array();
    
    for (let k = left; k < right + 1; k++) {
        let i = Math.floor(k / n);
        let j = k % n;
        arr.push(Math.max(i + 1, j + 1));
    }
    
    return arr;
}

`k`를 통해 `i`와 `j`를 모두 구해,

하나의 반복문으로 2차원 배열을 만드는 것처럼 했다.

시작은 ``left``, 끝은 ``right``로 하여 필요한 값만 생성했다.

 

시간도 잘 나왔고 모든 케이스를 통과했다.

왠지 모르겠지만, 괜히 재미있었던 것 같다.

규칙이 바로 보여서 그랬던 것 같기도 하고...