lv2 / n^2 배열 자르기 / C++

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

프로그래머스

---

이 문제를 실제로 2차원 배열로 만들어서 일일이 1차원 배열로 바꾸고, 이를 자르는 구현을 한다면 뭐 당연히 시간초과나 메모리초과 둘중하나는 무조건 뜰 것이다. n의 최댓값이 10^7인데, n X n 크기의 2차원 배열을 만든다면, 10^14개의 int가 들어가고, 여기서 메모리 초과가 당연히 날 것. 결국 우리는 배열을 만드는 것이 아닌, i행 j열의 숫자를 i와 j를 통해 일반화하여, 그 숫자를 알아내야 한다.

 

위 문제의 예제 1을 보자(n = 3, left = 2, right = 5). 2차원 배열을 구성하면 다음과 같다.

1	2	3
2	2	3
3	3	3

그리고 행과 열을 같이 한번 적어본다.

(0, 0) 1	(0, 1) 2	(0, 2) 3
(1, 0) 2	(1, 1) 2	(1, 2) 3
(2, 0) 3	(2, 1) 3	(2, 2) 3

 

복잡한 일반화된 공식을 만들어야하나라고 생각하던 찰나, 행, 열 값에 1을 더하면, 반드시 두 숫자중 하나는 해당 칸의 숫자가 된다는 것을 발견했다. 예를 들면 (0, 0)칸의 행, 열에 1씩 더하면 1,1이 되고, 이 칸은 1이 된다. (0, 2) 칸은 1, 3이고, 이 칸은 3이다. 이 규칙에 착안하여, 1차원 배열로 변형한 인덱스값을 다시 2차원 배열의 행, 열값으로 바꾸고, 이 값에 1씩 더한 후, 더 큰 값이 해당 칸의 값이 된다.

 

 [left, right] 구간을 모두 순차적으로 진행하기 때문에, 이 역시 시간초과가 날 것 같지만, 구간의 길이가 10^5를 넘지 않는다는 조건이 있기 때문에, 시간초과가 날 일은 없다.

 

#include <bits/stdc++.h>
using namespace std;

int slice_array_idx(long long idx, int n) {
    int quotient = idx / n + 1; // 몫
    int remainder = idx % n + 1; // 나머지
    
    return quotient > remainder ? quotient : remainder;
}

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    for(auto i = left; i <= right; i++) answer.push_back(slice_array_idx(i, n));
    return answer;
}