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

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

프로그래머스

---

문제풀이

N^2 배열을 만들려고 봤더니 N의 크기가 1억이었다. 이걸로 2차원 배열을 만들면 너무 커지기 때문에 배열을 모두 만들어 쪼개는 것은 불가능하다고 생각했다. 그래서 규칙을 찾아보았다. 그 결과 다음과 같은 규칙을 찾을 수 있었다.

(r, c)의 값은 r, c 중에 더 큰값에 1을 더한것이다. 예를들어 (1,3)일 경우에 해당 배열에 들어갈 값은 4가 된다. 이런 방법을 사용해 left index부터 right index의 값을 계산 할 수 있었다. 반복을 돌면서 r은 해당 값을 n으로 나눈 몫이고, c는 해당 값을 n으로 나눈 나머지이다. 이 값에서 더 큰값에 1을 더해주면 해당 위치의 값이 된다. 이걸 정답에 추가해 주면 간단하게 풀 수 있다.

 

 #include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    answer.reserve(100000);
    for(long long i = left; i <= right; i++) {
        long long r = i/n;
        long long c = i%n;
        if(r >= c) {
            answer.push_back(r+1);
        }
        else {
            answer.push_back(c+1);
        }
    }
    return answer;
}