[Lv 2] n^2 배열 자르기

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

프로그래머스

 

문제에서 2차원 배열을 1차원으로 바꾼 후 left와 right 범위로 배열을 자르라고 요구하지만 2차원 배열을 만들 수 없다.

이유는 n의 최대 범위가 10^7이기 때문에 2차원으로 배열을 생성 시 overflow가 발생할 수 있다.

따라서 2차원을 1차원으로 바꾸는 것이 아닌 원래 1차원으로 배열을 만들어야 함을 알 수 있다.

 

n이 주어질 때 배열은 아래와 같이 만들어진다.

n이 3인 경우 배열은 123 223 333이 된다.

또한 n이 4인 경우 배열은 1234 2234 3334 4444가 된다.

 

위 경우를 생각해보면 i번째 인덱스의 값은 n에 따라 결정되는 것을 알 수 있다.

n이 3이고 i가 2일 경우 3이된다. 또한 i가 5일 경우 3이 된다.

즉, i 와 n을 나눈 나머지에 1을 더한 값이 배열의 값이 되는 것을 알 수 있다.

 

하지만 다른 경우를 보면 i가 6인 경우와 7인 경우고 3이 된다.

이 경우는 i와 n을 나눈 값에 1을 더한 값임을 알 수 있다.

 

나눈 값을 사용하거나 나머지 값을 사용하는 경우는 2개의 값 중 큰 값을 사용하면 된다.

 

#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; i<= right; i++){
        long long x = i / n;
        long long y = i % n;
        if(x < y) answer.push_back(y + 1);
        else answer.push_back(x + 1);
    }
    
    return answer;
}