문제

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

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

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

해결

우선 처음 떠올린 방법은 완전탐색이었다. 그러나 n의 범위가 10000000까지, left와 right의 범위가 n^2까지 였으므로 다른 방법을 생각해보았다.

일단 해당 2차원 배열이 가지는 규칙을 살펴보자. i번째 행은 i번재 열까지 i의 값을 갖고, 그 이후의 열은 순서대로 +1의 값을 가진다. 이것을 1차원 배열로 이어붙인 것이 문제에서 요구하는 배열이다. 그렇다면 다음과 같은 반복문을 통해 시작점부터의 1차원 배열을 구할 수 있다.

while(1) {
        for (int i = y; i <= n; i++) {
            if (i <= x) answer.push_back(x);
            else answer.push_back(i);
            
            if (answer.size() == right - left + 1) return answer;
        }
        x++;
        y = 1;
    }

이 코드에서 for문은 하나의 행이 된다. 규칙에 따라 각각의 열에 들어가는 값을 1차원 배열인 answer 벡터에 넣어준다. 다음 행으로 넘어가기 위해 행번호(x)에 +1을 해주고 열번호(y)를 1로 초기화한다. 이 때 구하고자 하는 배열의 크기는 right-left+1이므로 해당 크기에 도달하면 return 한다.

이제 이 반복문의 시작점을 구해주어야 한다. 시작점은 left와 n을 통해 구할 수 있다. 하나의 행의 크기는 n이고 left를 n으로 나눈 몫은 행번호, n으로 나눈 나머지는 열번호가 된다. 그러므로 x에 left/n+1을 저장, y에 left%n+1을 저장 후, 해당 반복문을 돌면 원하는 배열을 구할 수 있게 된다. (인덱스는 0부터 시작하지만 값은 1부터 저장되므로 +1을 해주었다.)

따라서 전체 코드는 다음과 같다.

#include <vector>
using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    int x = left / n + 1;
    int y = left % n + 1;

    while(1) {
        for (int i = y; i <= n; i++) {
            if (i <= x) answer.push_back(x);
            else answer.push_back(i);

            if (answer.size() == right - left + 1) return answer;
        }
        x++;
        y = 1;
    }
}