[C++] n^2 배열 자르기

 

n^2 배열 자르기

정수 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

 

 

입출력 예

3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

 

 

 

 

처음 배열을 만들어 위 사진과 같이 할당하고자 했는데, 배열로 만들면 시간초과 또는 메모리 오버가 발생하였습니다.

 

그래서 규칙을 찾아내고, left, right 범위의 해당하는 값을 찾아냈습니다. 직접 N이 3, 4, 5 일때, 배열을 펴보면 됩니다.

위 사진을 보면, 배열이 펼쳐져 있을때 123 223 333, 1234 2234 3334 4444, ... 로 나오는데 각 해당하는 인덱스를 기준으로 규칙을 찾으면 됩니다. 즉, 인덱스를 N으로 나눈 몫과 나머지에 힌트가 있습니다.

 

예를들어 N이 3이면,

 

인덱스가 0인 경우 --- 몫 0, 나머지 0, 값 1

인덱스가 1인 경우 --- 몫 0, 나머지 1, 값 2

인덱스가 2인 경우 --- 몫 0, 나머지 2, 값 3

 

인덱스가 3인 경우 --- 몫 1, 나머지 0, 값 2

인덱스가 4인 경우 --- 몫 1, 나머지 1, 값 2

인덱스가 5인 경우 --- 몫 1, 나머지 2, 값 3

 

인덱스가 6인 경우 --- 몫 2, 나머지 0, 값 3

인덱스가 7인 경우 --- 몫 2, 나머지 1, 값 3

인덱스가 8인 경우 --- 몫 2, 나머지 2, 값 3

 

위 값은 몫이 나머지보다 크거나 같으면, 나머지 + 1이 되고 몫이 나머지보다 작으면 몫 + 1 이 됩니다. 이 규칙을 코드로 나타내면 아래와 같습니다.

 

주의할 점은 long long 타입형을 사용하여 left, right 값을 받기 때문에, 변수를 선언할 때 long long  타입형을 사용해야 합니다.

 

 

풀이

#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 + 1; i++){
        (i / n) <= (i % n) ? answer.push_back(i % n + 1) : answer.push_back(i / n + 1);
    }
    return answer;
}

 

 

 

오답 (배열사용)

// 배열로 풀 경우 시간초과

vector<int> solution(int n, long long left, long long right) {
    vector<int> arr;
    vector<int> answer;
    int num1 = 1, num2 = 1;
    for(int i = 1; i < n + 1; i ++){
        for(int j = 1; j < n + 1; j++){
            if(j < num1){
                arr.push_back(num1);
            }
            else{
                arr.push_back(j);
            }
        }
        num1++;
    }
    for(int i = left ; i < right + 1; i++){
        answer.push_back(arr[i]);
    }
    return answer;
}