N x N 배열 자르기

 

🔎2차원 배열에서 주어진 규칙으로 1차원 배열 만드는 과정 예시

{0, 0} 좌표 1부터 시작해서 주변의 노드를 1씩 더해 채운다

 

1차원 배열로 만든 뒤, left ~ right 요소를 제외하고 삭제

 

 

 

✅ Flood - Fill 알고리즘으로 2차원 배열 세팅 ver

#include <string>
#include <vector>
#include <queue>

using namespace std;

void make_flood(vector<vector<int>>& map, const int& n)
{
    struct Node
    {
        int y, x;
    };
    
    int direct[8][2] = {
        -1,0,
        -1,1,
         0,1,
         1,1,
         1,0,
         1,-1,
         0,-1,
        -1,-1
    };

    queue<Node> q;

    map[0][0] = 1;
    q.push({ 0,0 });

    while (!q.empty())
    {
        Node now = q.front();
        q.pop();

        for (int i = 0; i < 8; ++i)
        {
            int dy = now.y + direct[i][0];
            int dx = now.x + direct[i][1];
            if (dy < 0 || dx < 0 || dy >= n || dx >= n) continue;
            if (map[dy][dx] != 0) continue;

            map[dy][dx] = map[now.y][now.x] + 1;
            q.push({ dy,dx });
        }
    }
}

vector<int> solution(int n, long long left, long long right)
{
    // flood fill 알고리즘으로 map 세팅
    vector<vector<int>> map(n, vector<int>(n, 0));
    make_flood(map, n);

    // 1차원 배열로 변환
    vector<int> answer;
    for (const auto& row : map)
    {
        answer.insert(answer.end(), row.begin(), row.end());
    }

    // left, right 사이의 요소 제외하고 삭제
    answer.erase(answer.begin(), answer.begin() + left);
    answer.erase(answer.begin() + (right - left + 1), answer.end());

    return answer;
}

문제의 입출력 예에서 나오는 케이스들은 통과하였지만, 제한사항의 n값을 확인하지 않고 map을 2차원 배열로 만들었던게 문제가 되었다.
vector<vector<int>> map(n, vector<int>(n, 0)); 크기가 n x n인 2차원 배열을 메모리에 할당하는데, n의 최대값이 10의 7제곱이므로 메모리 사용량이 엄청났던 것이다.
2차원 배열을 메모리에 할당하지 않고, 1차원 배열로 값을 계산해야된다는 것을 확인했다.

 

 

✅ 수정 코드

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, long long left, long long right) 
{
    vector<int> answer;
    answer.reserve(right - left + 1);  // 메모리 미리 할당

    // left에서 right까지 필요한 값만 바로 계산
    for (long long i = left; i <= right; ++i) {
        int row = i / n;
        int col = i % n;
        answer.push_back(max(row, col) + 1);
    }

    return answer;
}

 

행렬에서 필요한 부분(left ~ right)만 1차원 배열에 직접 채우는 방식으로 재구현

🔎2차원 배열을 1차원 배열로 변환하는 공식

i = row × n + col

여기서 n이 3이라고 가정한다면 아래와 같이 변환할 수 있다.

(0, 0) = 0
(0, 1) = 1
(0, 2) = 2
(1, 0) = 3
(1, 1) = 4
(1, 2) = 5
(2, 0) = 6
(2, 1) = 7
(2, 2) = 8

• row = i / n: i를 행당 열의 개수 n으로 나누면 몇 번째 행인지 알 수 있다.
• col = i % n: i를 n으로 나눈 나머지로 몇 번째 열인지를 알 수 있다.