[Programmers] Lv2. n^2 배열 자르기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

\(n\)의 최대 개수가 천만 개라, 2차원 배열을 만들어 수를 저장하고, 나눗셈과 몫 연산을 통해 left ~ right 사이의 숫자만 추출하면 되지 않을까 생각하여 코드를 짰는데, 시간 초과가 났습니다. 시간을 더 줄일 방도가 필요했습니다.

방법을 모색하던 중, (i, j)에 저장되는 숫자는 max(i + 1, j + 1)이라는 특성을 발견하였습니다.

    0 1 2 3
  ---------
0 | 1 2 3 4
1 | 2 2 3 4
2 | 3 3 3 4
3 | 4 4 4 4

// #1
(0, 2)에 적힌 숫자는?  -> max(0 + 1, 2 + 1) = 3

// #2
(3, 1)에 적힌 숫자는?  -> max(3 + 1, 1 + 1) = 4

 

이와 같은 특성과 행 = left / n, 열 = left % n을 이용한다면 빠르게 구할 수 있습니다.

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;

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

    int row = left / n;
    int col = left % n;
    int count = right - left + 1;

    for (int i = 0; i < count; i++) {
        int num = max(row + 1, col + 1);
        answer.push_back(num);
        col++;

        if (col == n) {
            row += 1;
            col = 0;
        }
    }

    return answer;
}