[Programmers] 프로그래머스 Lv.2 n^2 배열 자르기 문제풀이(C++) - 월간 코드 챌린지 시즌3

수열의 규칙을 생각해내야 했던 문제 - 내 느낌상 Lv.3 였음ㅠ

처음에 그대로 구현하려다가 n 제한이 10^7인 것과 left, right가 long long으로 선언된거 보고 배열 구현은 절대 아니겠다는 생각이 들었고, 이후 떠오른게 규칙성임

 

#include <string>
#include <vector>
 
using namespace std;
/*
<문제>
n*n 2차원배열
 
i=1~n 반복 - O(n)
  (1, 1) ~ (i, i) 모든 '빈칸'을 i로 채움 - O(i^2)
1~n행 잘라내서 모두 이어붙인 1차원 배열 arr생성 - O(n*i)
arr[left]~arr[right]만 남김 -> 이걸 return하기 - O(right-left)
 
<풀이>
(i가 i번 나오고 나머지 n번째까지 빈 배열) -> 이걸 i번 이어붙이면 됨
여기서 left~right까지 자르기
 
배열 규칙을 생각해내야함 / n=4이면 1234 2234 3334 4444 / 
n이 8이면 12345678 22345678 3334'5'678 44445678 55555678 66666678 77777778 88888888
 -> 이 수열이 a일때, x번째 항 a(x)를 구하는 식을 구하면 됨 / 따옴표를 타겟으로 일반화할거
 
x : 목표 번호(left나 right) -> 20
n : 행렬 크기 -> 8
 
덩어리인덱스 = x/n -> 2
덩어리 내부 인덱스 = x%n -> 4
 
if(x%n <= x/n) a(x) = x/n+1
else a(x) = x%n+1
 
<시간>
O(right-left)
 
*/
vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    vector<vector<int> > num;   //숫자들
    
    for(long long x=left; x<=right; x++){
        
        if(x%n <= x/n) answer.push_back(x/n+1);
        else answer.push_back( x%n+1 );
        
    }
    
    
    return answer;
}