프로그래머스 - n^2 배열 자르기 [C++]

 이 문제는 규칙성을 찾아 그대로 구현해서 푸는 문제이다. 일단 n의 최대 크기가 1,000만이므로 2차원 배열 자체를 만들 수 없다. 또한 n x n 배열을 1차원 배열로 만들어놓은 배열 또한 만들 수 없다. 그러므로 단순한 탐색 알고리즘으로는 불가능하고, 숫자에서 규칙을 찾아 문제를 풀어야 한다.

 

 

 일단 right - left 가 최대 99,999 이므로 answer 배열의 최대 길이는 100,000이 될 것이다. 이 문제의 핵심은 left와 right로 주어진 숫자를 2차원 배열의 몇행 몇열인지를 한번에 찾아내는 것이다. 간단한 방법이 있었는데, 만약 숫자가 7이고, 4 x 4 배열이라고 가정하면 7 / 4 = 1, 7 % 4 = 3 으로 0번 인덱스부터 시작해서 1행 3열을 나타내는 수가 7이 되는 것이다. 

 

 

 또 중요한 것은 2번 조건을 잘 이해하는 것인데, 4 x 4 배열에서 2번 조건을 수행한 후 배열의 숫자는

1 2 3 4

2 2 3 4

3 3 3 4

4 4 4 4

가 된다. 이번에는 행과 열의 인덱스가 1부터 시작한다고 했을 때, 각 요소가 나타내는 행과 열 중 큰수가 저장되어있음을 알 수 있다. 예를 들어 3행 4열의 경우 4가 저장되는 것이다. 이 두 사실을 조합해서 코드로 구현하면 시간 안에 구현할 수 있다.

 

 

 

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

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    long long leftRow = left / n + 1;
    long long leftCol = left % n + 1;
    
    long long rightRow = right / n + 1;
    long long rightCol = right % n + 1;
    
    // base case
    if (leftRow == rightRow && leftCol == rightCol) {
        answer.push_back(max(leftRow, leftCol));
        
        return answer;
    }
    
    long long row = leftRow;
    long long col = leftCol;
    
    while (!(row == rightRow && col == rightCol)) {
        answer.push_back(max(row, col));
        
        col++;
        if (col > n) {
            col = 1;
            row++;
        }
    }
    answer.push_back(max(rightRow, rightCol));
    
    return answer;
}