프로그래머스 87390 - n^2 배열 자르기 (Lv.2)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/87390

// 프로그래머스 87390 - n^2 배열 자르기 (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/87390

// 문제 설명
// n x n 배열을 만들어 i행 j열(1-based)에 max(i, j)를 채운 뒤,
// 행 우선으로 1차원으로 펴서 left..right(0-based, 양 끝 포함) 구간을 반환하라.

// 제약 조건
// 1 <= n <= 10^7
// 0 <= left <= right < n^2
// right - left < 10^5

// Example
// Input : n = 3, left = 2, right = 5
// Output: [3, 2, 2, 3]
//   배열 [1,2,3 / 2,2,3 / 3,3,3]을 펴면 [1,2,3,2,2,3,3,3,3], 인덱스 2..5는 [3,2,2,3]

// 접근 — 배열을 만들지 않고 인덱스에서 값을 역산
// 1) n^2이 최대 10^14라 배열을 실제로 만들면 시간도 메모리도 불가능.
//    답으로 요구되는 구간은 최대 10^5개뿐이므로 그 인덱스만 계산한다.
// 2) 1차원 인덱스 k의 좌표는 행 = k / n, 열 = k % n (0-based).
//    0-based에서 이 칸의 값은 max(행, 열) + 1 이다.
// 3) k가 n^2 - 1까지 가므로 int 범위를 넘는다 → long long으로 순회.
// 시간 O(right - left), 공간 O(right - left)

#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);

    for (long long k = left; k <= right; k++)           // 1차원 인덱스 k만 순회
        answer.push_back((int)(max(k / n, k % n) + 1)); // (행, 열) = (k/n, k%n), 값 = max+1
    return answer;
}

정리

• 문제 지문은 “배열을 만들어 펴라”고 하지만 제약(n 최대 10^7, n² 최대 10^14)이 배열 생성 자체를 금지하고 있다. 반면 답 구간은 최대 10^5개. “만들어서 자르기”가 아니라 “필요한 칸만 역산하기” 문제로 뒤집어 읽어야 한다.
• 행 우선으로 편 1차원 인덱스 k는 (행, 열) = (k / n, k % n)으로 즉시 2차원 좌표로 돌아간다. 이 평탄화(flatten) ↔ 복원 공식은 2차원 배열을 1차원 버퍼로 다루는 모든 곳(이미지, 행렬)에서 그대로 쓰인다.
• 칸의 값이 max(행, 열) + 1인 이유: 이 배열은 1을 (1,1)에, 2를 2행 2열 테두리에, i를 i행 i열의 ㄱ자 테두리에 채운 모양이라, 어떤 칸의 값은 두 좌표 중 큰 쪽이 결정한다. 예제 3x3 배열 [1,2,3 / 2,2,3 / 3,3,3]에서 규칙을 손으로 확인하고 공식화하면 된다.
• left, right가 최대 10^14라 인덱스 변수를 int로 돌리면 오버플로다. 매개변수부터 long long으로 받고 루프 변수도 맞춘다. 값 자체는 최대 n(10^7)이라 결과는 int에 안전하게 들어간다.
• 검증: 예제 (3, 2, 5) → [3,2,2,3], (4, 7, 14) → [4,3,3,3,4,4,4,4] 통과(MSVC /std:c++17 컴파일·실행).