[프로그래머스 lv2] n^2 배열 자르기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

가장 먼저 해당 문제가 완전 탐색이나 단순 구현으로 해결되는지 확인해야한다.

최대 입력 범위가 10^7 이기 때문에 반복문으로 배열의 행과 열을 채우면 TLE가 발생한다.

따라서 배열을 일렬로 나열했을 때의 인덱스를 보고 바로 배열의 값을 알아낼 수 있는 방법을 찾아야 한다.

 

일단, 배열의 x, y 좌표와 배열 값 사이의 관계를 생각해보면, (x, y)의 값은 max(x, y) + 1 이 된다.

 

 

예를 들어, (2, 3)의 값은 max(2, 3)+1 = 4 가 되고, (2, 0)의 값은 max(2, 0)+1 = 3 이 된다.

해당 규칙을 이용하면 각 배열을 모두 순회하지 않고도 특정 좌표의 값을 바로 알 수 있다.

 

다음으로, 배열을 일렬로 나열했을 때의 인덱스와 2차원 배열에서의 행, 열 값의 관계를 생각해보자.

1차원 배열에서의 인덱스가 i일 때, 2차원 배열에서의 행은 i/n, 열은 i%n이 된다. (n은 배열의 가로, 세로 크기)

 

정리해보면, 1차원 배열의 인덱스 i번째 원소는 2차원 배열에서의 (i/n, i%n) 좌표 값이 되고, (i/n, i%n) 좌표의 값은 max(i/n, i%n)+1 이 된다.

 

문제에서는 left와 right 인덱스 사이의 값을 요구하고 있으므로, 사이의 인덱스를 순회하며 max(i/n, i%n)+1 값을 구하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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

    vector<int> v;
    for (long long i=left; i<=right; i++)
        v.push_back(max(i/n, i%n)+1);
    return v;
}