[Programmers] Level2 : n^2 배열 자르기

Question

---

Solution

• 2차원 배열을 1차원으로 변환한다. 이를 위해 이중for 루프를 하거나, 모든 1차원 배열을 만들고자 하면 시간 초과가 난다.
• 주어진 left와 right를 가지고 해당 필요 범위만 뽑아내야 한다.
• 2차원 배열에서의 idx는 1차원 배열 에서의 idx와 이러한 관계를 가진다.
  1차원 idx = row * n + column
  row = i/n, column = i%n
• 그리고 해당 idx의 값은 ‘1차원의 값 = row와 column 중 가장 큰 것의 + 1’ 와 같은 관계가 성립 된다.

---

Cord

#include <string>
#include <vector>

using namespace std;

// 2차원을 1차원으로 변환
// 1차원 idx = row * n + column
// 1차원의 값 = row와 column 중 가장 큰 것의 + 1
// row = i/n, column = i%n
vector<int> solution(int n, long long left, long long right) 
{
    vector<int> answer;
    
    // left와 right 사이의 값을 answer에 push
    for (long long i = left; i <= right; ++i)
    {
        int row = i/n;
        int column = i%n;
        int bigger = 0;
        
        if (row >= column)
        {
            bigger = i/n + 1;
        }
        else
        {
            bigger = i%n + 1;
        }
        
        answer.push_back(bigger);
    }
    
    return answer;
}

/*
1차원   2차원     값    [i/n][i%n]
0 1 2  00 01 02  1 2 3  00 01 02
3 4 5  10 11 12  2 2 3  10 11 12
6 7 8  20 21 22  3 3 3  20 21 22
*/

---

Result