[프로그래머스 - JS] level.2 n^2 배열 자르기

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

프로그래머스

---

나의 풀이 

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

와 이 문제는 계속 시간초과가 나서  계속 바꿔 풀었는데 안되어서 블로그를 보고 풀었다. 

 

일단은 이 문제를 풀려면 기초개념이 필요하다. 

일단 시간 복잡도 계산을 할 줄 알아야하고 자바스크립트가 수를 어디까지 표현할 수 있는지 알아야한다. 

 

즉 

1. 문제에서는 2차원 배열을 만들고나서 1차원배열로 만들고, left부터 right까지를 출력하라고 했으나, 애초에 n의 최대값이 10^7이므로 2차원 배열을 만드는 순간 물리적으로 O(10^14)가 필요해서 무조건 시간초과이다. (대강 O(10^9)을 1초로 잡으면 되므로 10만초임)2. 마찬가지로, 1차원 배열로 바꾸는것도 O(10^14)이므로 하면 안됨.3. 그럼 남은건 left부터 right까지에 대해 right - left < 10^5 이므로 left부터 right까지 각 O(1)로 원하는 값을 찾을 수 있어야 한다.
 
  결론적으로 특정 (r, c) 위치의 값을 O(1)로 구할 수 있으면 된다. 공책에 좀 그려보면 규칙성을 찾을 수 있는데, max(r, c)+1이 해당 칸의 값이 된다. 그렇다면 left부터 right까지 1차원 배열의 인덱스값을 가지고 원래의 (r, c) 위치만 찾을 수 있다면 답을 구할 수 있다. 이건 1차원 배열에서의 인덱스가 x라고 할 때, x/n이 r값이고 x%n이 c값이다.

출처:Nahwasa 티스토리 블로그

이런식으로 생각을 해야 수월하게 풀 수 있다. 

하지만 나에게는 이런 것들이 부족하기에  이 개념붙어 잡고 가야겠다. 

 

또한 이렇게 생각이 되었다면 나머지는 손으로 풀어가면 규칙찾기를 해주면된다. 

그리고 그 규칙을 코드로 작성한 것이 위의 기록된 것이다. 

 

처음 실패한 코드는 아래와 같다. 

function solution(n, left, right) {
    let result = []
    let save = Math.floor(left/n)
    let limit = n**2 - n
    let t = 0
    while(right <= n**2 - (t+1)*n){
        t++
    }
    for(i=save; i< n-t; i++){
        let standard = i + 1;
        let line =[]
        for(k=0; k<n; k++){
            line[k] = standard <= k + 1 ? k + 1 : standard
        }
        result.push(...line)
    }
    return result.slice( left - (save*n),right+1 - (save*n))
}

필자는 2차원 배열을 전부 만들고 다시 1차원 배열로 바꾼뒤 해당 구역만 return하는 것으로 코드를 짰다. 

이렇게 하면 60점이나온다. 

즉 너무 큰 수는 이중 for문으로 인해 또는 while과정 때문에  런타임 오류가 뜬다. 

n이 엄청 큰 수이면 n**2를 하면 감당이 되지 않기에  이 방법은 불가능 할 것 같다. 

 

다른 사람 풀이 보니 전부 규칙을 찾아 푼 것이라는 베이스는 같았다. 

이렇게 2차원 배열을 1차원으로 해서 풀 수는 없는 것 같다.