Level 2️⃣ - n^2 배열 자르기

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

프로그래머스

🚀문제 해석

n이 최대 10^7 이기 때문에 이차원배열을 만들어 요소를 집어넣고 다시 1차원배열로 만들어서 left에서 right까지 자른다고 생각하면 시간복잡도 초과가 날 것이다. 왜냐하면 최악의 경우 이차원 배열을 만드는 데 10^14번까지 연산이 이루어지기 때문이다. 

이런 문제는 규칙 혹은 패턴을 찾아야한다.

 

이차원 배열이니까 좌표로 접근해보자.

그림과 같이 arr[ i ][ j ] 좌표에 들어갈 숫자는 i와 j의 최댓값에서 1을 더한 값이다.

left와 right는 1차원 배열에서의 인덱스 정보이기 때문에 2차원 배열에서는 어떤 좌표에 해당하는지 알아야한다.

그림에서 설명하는 것과 같이 left와 right까지의 모든 숫자에 n을 나눈값과 n으로 나눴을 때 나머지가 이차원 배열에서의 좌표에 해당한다. 그렇다면 해당 좌표에 들어가는 숫자는 좌표값들의 최댓값에서 1을 더해주면 된다.

이렇게 하면 left에서 right까지의 한번의 연산으로 문제를 해결할 수 있기 때문에 시간복잡도에서 효율성이 매우 높아진다.

 

🛠코드

function solution(n, left, right) {
    let ret = [];
    for(let i = left; i<=right; i++) ret.push(Math.max(Math.floor(i / n), i % n) + 1);
    return ret;
}

 

코드는 굉장히 짧다.

결국에는 패턴을 찾는 것이 관건인 문제였다.

1차원 배열에서의 위치를 2차원 배열에서의 좌표로 변환하는 과정 을 배웠다. 나중에 유사한 문제가 나왔을 때 까먹지 않도록 복습해야겠다.