[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

---

오답노트

ㄴ 처음엔 그냥 2중포문으로 전부 구했더니 시간 초과

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
	vector<int> answer;
	/*
	1234
	2234
	3334
	4444

	1행은 1~n 순차적으로 증가
	..
	i행은 1~i까지 i로 채워지고 i+1~n 까지는 순차적으로 증가

	left는 left/n + 1행의 left%n 번째 숫자부터
	*/

	vector<long long> list; // right + 1 의 크기
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (j <= i)
				list.push_back(i);
			else
				list.push_back(j);
		}
	}

	for (int i = left; i <= right; i++)
		answer.push_back(list[i]);

	return answer;
}

 

 

그래서 left와 right가 포함되는 행의 원소들을 모두 구하고,

left와 right를 이용해서 시작과 끝지점 사이의 값만 정한뒤, 해당 구간만큼만 answer에 넣어서 해결했다.

#include <string>
#include <vector>

using namespace std;

// 해당 행에 포함되는 원소를 구하는 함수
vector<int> InsertRow(int row, int n)
{
	vector<int> list;
	// i행은 1~i까지 i로 채워지고 i + 1~n 까지는 순차적으로 증가
	for (int idx = 1; idx <= n; idx++)
	{
		if (idx <= row)
			list.push_back(row);
		else
			list.push_back(idx);
	}

	return list;
}

vector<int> solution(int n, long long left, long long right) {
	vector<int> answer;
	vector<int> temp;
	// 행 부터 구하기
	long long startRow = left / n + 1;
	long long endRow = right / n + 1;
	for (long long i = startRow; i <= endRow; i++)
	{
		auto v = InsertRow(i, n);
		temp.insert(temp.end(), v.begin(), v.end());
	}

	// 시작과 끝 지점을 정해서 해당 사이만 정답에 복사한다.
	long long offsetStart = left % n;
	long long offsetEnd = n - right % n - 1;
	answer.insert(answer.end(), temp.begin() + offsetStart, temp.end() - offsetEnd);

	return answer;
}

 

 

근데 더 간단히 하려면 사실 바로 행과 열의 값을 이용해 원소에 들어갈 값을 구하면 된다.

어차피 특정 행의 원소값이 해당 행보다 작으면 해당 원소값은 행으로 넣어지기 때문에 max를 활용해서 구할 수가 있다..

long long row = i / n + 1;
long long col = i % n + 1;
// 각 위치의 값을 계산하여 answer에 추가
answer.push_back(max(row, col));

이걸 이용하면

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    int row;
    int column;
    for(long long i = left; i <= right; i++){
        answer.push_back(max(i / n, i % n) + 1); // 헹과 열을 바로 구해서 행보다 작으면 무조건 행이 들어가는 걸 이용
    }

    return answer;
}

이렇게 간단히 끝낼 수 있었다....

접근 방법

ㄴ left와 right 가 주어졌으므로, 이를 활용해서 left~right 의 순회를 이용해 구할 수 있는 방향으로 생각했어야 한다.