[Programmers] n^2 배열 자르기

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

프로그래머스

 

---

 

문제 해결 과정

착안

$n \times n$ 크기의 행렬 matrix[][]는 한 행에 $n$ 개의 요소를 가지므로, 각각의 행을 이어붙여 1차원 배열로 만들었을 때의 $k$ $(1 \le k \le n^2)$ 번째 요소는 $k$ 를 $n$으로 나눈 몫을 $q$, 나머지를 $r$ 이라고 했을 때 matrix[$q$][$r$] 이다.

 

한편, 문제에서 주어진 규칙에 따라 $n \times n$ 크기의 행렬을 초기화하면

• $i \ge j$ 인 경우: matrix[$i$][$j$] $= i + 1$
• $i < j$ 인 경우: matrix[$i$][$j$] $= j + 1$

이다. 위의 두 사실을 활용하면 행렬을 만들지 않고 left 번째부터 right 번째까지 요소에 해당하는 값들을 구할 수 있다.

 

구현

left 번째의 요소가 $n \times n$ 행렬 내에서 몇 번째 행, 열에 위치하는지를 구한 다음, 반복문을 통해 열을 가리키는 인덱스를 1 씩 증가시키면서 $k$ 번째 요소의 값을 구한다. 열을 나타내는 인덱스가 $n$이 되면 행을 가리키는 인덱스를 1 증가시키고 열을 가리키는 인덱스를 0 부터 다시 시작한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right)
{
    vector<int> answer;
    long long row = left / n, col = left % n;
    for (long long i = left; i <= right; i++)
    {
        answer.push_back(row < col ? col + 1 : row + 1);
        if (++col == n)
        {
            row++;
            col = 0;
        }
    }
    
    return answer;
}

 

실행 결과