문제 살펴보기

위에 gif에서 보는 것 처럼 n^2배열을 생성한 후 이를 일렬로 나열한 다음에 left~right의 인덱스에 있는 원소를 출력하면 되는 문제이다. "왜 이 문제가 2레벨일까?"하는 의문이 들 정도로 간단해 보이지만 사실은 그렇지 않다.
저 친절한 gif는 함정이다.
저 설명만 믿고 코드를 구현한다면 (signal: aborted (core dumped))라는 오류를 만나게 된다.

(signal: aborted (core dumped)) 오류는 프로그램이 예외 상황에 직면해 종료되었거나, 시스템 리소스 부족, 잘못된 메모리 액세스, 스택 오버플로우 등의 이유로 발생한다. 이 문제에서는 2차원 배열의 사이즈때문에 문제가 생긴 것 같다.
그렇다면, 2차원배열을 사용하지 않고 문제를 해결해야 한다.
이 문제의 제한사항을 읽어보면 n의 범위가 1 <= n <= 10^7인 것을 알 수 있는데 javascript 배열의 최대 길이는 4294967296(2^32)미만 이기 때문에 n*n = 10^14 크기의 1차원 배열을 생성하는 것도 불가능하다.
결국 남은 방법은 left ~ right까지 반복문을 돌면서 해당하는 인덱스의 값을 계산해주는 것이다.

구현하기

몫과 나머지 연산을 이용해서 배열의 열과 행에 접근할 수 있다

아래 그림과 함께 자세하게 알아보자.

위의 그림에서 2차원 배열을 a, 평탄화된 배열을 b라고 지칭하도록 하겠다.
그렇다면 아래와 같은 등식이 성립한다.(n은 배열의 크기)

b[4] = a[⌊4/n⌋][4%n] = a[1][1]

따라서 몫과 나머지 연산을 활용하면 평탄화된 배열의 인덱스로 2차원 배열에 접근할 수 있다.
하지만 우리는 인덱스 안에 어떤 값이 들어있는지 알아야 한다.
일반적인 경우에는 배열에 값을 저장하지 않은 채 인덱스만으로 값을 알아내는 것은 불가능하지만, 이 문제에서 다루는 배열은 특정한 규칙을 갖고있기 때문에 값을 추론할 수 있다.

배열의 원소, 몫과 나머지의 관계 찾기

평탄화된 배열의 인덱스를 index라고 지칭할 때 다음과 같은 규칙을 발견할 수 있다.

각각 열에 대해 글로 풀어서 설명하자면 다음과 같이 설명할 수 있다.
0번째 열을 나타냄, 0번째 열의 원소는 1부터 시작되고, 1이 1만큼 반복된 후에 수가 하나씩 증가하는 형태임.
1번째 열을 나타냄, 1번째 열의 원소는 2부터 시작되고, 2이 2만큼 반복된 후에 수가 하나씩 증가하는 형태임.
2번째 열을 나타냄, 1번째 열의 원소는 3부터 시작되고, 3이 3만큼 반복된 후에 수가 하나씩 증가하는 형태임.

이제 남은 것은 수가 반복된 후에 증가하는 부분을 어떻게 처리해야 하는지이다.
위에 나열한 규칙을 잘 살펴보면 ⌊index/n⌋ >\= index%n일 때 까지는 ⌊index/n⌋ + 1가 원소값이 되고 이후에는 index%n + 1이 원소값이 되는 것을 발견할 수 있다.

코드 구현

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

위에서 발견한 규칙을 기반으로 위와 같이 간단하게 구현할 수 있다.

문제 후기

처음에 문제를 읽을 때 gif 설명을 보고 놀랐다.
이렇게나 친절한 문제가 있다니...!!
하지만 그 애니메이션대로 구현했더니 프로그래머스에서 처음 보는 (signal: aborted (core dumped))라는 오류를 맞닥뜨렸다.
그래서 좀 더 고민한 끝에 해결했다.
알고리즘 문제는 바로 해결할 때 보다 한번 난관에 부딪힐 때 더 많은 것을 배울 수 있는 것 같다.