C++, 프로그래머스2단계 n^2 배열자르기

0. 문제

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

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ n ≤ 10^7
0 ≤ left ≤ right < n^2
right - left < 10^5

1. 시간초과된 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> two_dim_arr(int n, int left, int right){
    vector<vector<int>> two(n, vector<int>(n));
    vector<int> answers;
    int count = 0;
    
    for(int i = 0; i < n; i++){
        int tuple = i + 1;
        for(int j = 0; j < n; j++){
            int cardi = j + 1;
            if(count >= left && count <= right){
                if(tuple >= cardi){
                    answers.push_back(tuple);
                }else{
                    answers.push_back(cardi);
                }     
            }
            count++;
        }
    }
    
    return answers;
}

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;

    answer = two_dim_arr(n, left, right);
    return answer;
}

• n*n 반복은 n 이 클 경우 시간초과를 불러일으킨다.

2. 시간초과를 해결한 풀이

• 2차원 배열 인덱스를 1차원배열로 표현한다면, [0, 1, 2, .. n-1, n, n + 1, ... 2n, 2n + 1, ...]

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;

    for(long long i = left / n; i <= right / n; i++) {
        for(long long j = (i == left / n) ? left % n : 0; j <= (i == right / n ? right % n : n-1); j++) {
            answer.push_back(max(i+1, j+1));
        }
    }

    return answer;
}

• 2차원 배열에서 특정위치 '(i,j)'에 들어가는 값은 'max(i,j)'와 같습니다.
• n*n 반복할 필요가 없다.
  1) 'left'와 'right'의 행 번호와 열번호를 계산합니다.'
  2) 'left'의 행 번호로부터 'right'의 행 번호까지 반복하며, 각 행의 시작 열 번호와 끝 열 번호를 계산합니다.
  3) 계산한 행 번호와 열 번호를 바탄으로 결과값을 'answer'에 추가합니다.