프로그래머스 - n^2 배열 자르기

✨ Lv. 2 - n^2 배열 자르기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87390

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.

• 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.

3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

풀이 코드 + 설명

처음 문제를 풀이할때는 상단의 입출력 예시를 기준으로 코드를 작성하였습니다. 해당 배열을 살펴보면, 1, 2, 3 / 2, 2, 3 / 3, 3, 3 으로 하나씩 뒤의 숫자가 반복되는 형태입니다. 이를 바탕으로 작성한 코드는 아래와 같습니다.

function solution(n, left, right) {
    let minimum = 1, array = [];
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            array.push(minimum > j + 1 ? minimum : j + 1);
        }
        minimum++;
    }
    
    return array.slice(left, right + 1);
}

하지만 이렇게 코드를 작성할 경우, 시간 초과가 발생하게 됩니다. 따라서 전체 배열을 생성한 후에 slice를 이용하여 자르는 방식이 아닌, 처음부터 잘린 상태의 배열을 구하여 return 하는 방식을 생각하였습니다.

left를 기준으로 minimum을 판단한 이후, 자른 상태의 배열의 값을 push하여 return 하였습니다.

function solution(n, left, right) {
    let minimum = Math.ceil((left + 1) / n), array = [];
    
    for(let i = left + 1; i <= right + 1; i++) {
        let current = i % n === 0 ? n : i % n;
        array.push(minimum > current ? minimum : current);
        if(i % n === 0) minimum++;
    }
    
    return array;
}

위 코드를 더 단순하게 작성할 수 있습니다. 현재 행에서의 최솟값은 현재 행의 index를 n으로 나눈 몫에 1을 더한 값과 동일하기 때문에, minimum을 따로 저장하지 않고 아래와 같이 작성하여 해결할 수 있습니다.

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