[프로그래머스] n^2 배열 자르기

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

코딩테스트 연습 - n^2 배열 자르기

 

다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

[풀이방법]

위의 애니메이션을 보면 1행, 2행, ... n행을 붙여 1차원 배열을 만들게 되면

1, 2, ... n | 2, 2,... n | 3, 3, 3, ... n |n, n, n, ... n, n, n|

이런식으로 배열이 생기게 되는데

x행의 경우, x를 x번 반복한 후(x, x, ..., x) x+1, x+2... n까지의 수를 한번씩 반복하게 된다.

 

따라서, 시작하는 좌표(left_y, left_x)를 구한 후, right_y 까지의 수를 append 하면 된다.

그렇게 되면 두번째 예시일때,

1	2	3	4
2	2	3	4
3	3	3	4
4	4	4	4

(두번째줄 4번째칸 ~ 4번째줄 전체)

4 | 3, 3, 3, 4 | 4, 4, 4, 4 | 

가 되는데 총 구해야 하는 배열의 길이는 left - right+1 이기 때문에, 위에서 append 하여 저장한 vector 의 0~left - right+1 까지의 값들을 답으로 리턴해주면 된다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    int left_y = left / n;
    int left_x = (left % n)+1;
    
    int right_y = right / n;
    
    int y = left_y;
    int x = left_x;
    while(y <= right_y) {
        
        for(int i=x; i<=n; i++) {
            if(i<y+1)
                answer.push_back(y+1);
            else
                answer.push_back(i);
        }    
        y += 1;
        x = 1;
    }
    
    vector <int> ret;
    for(int i=0; i<right-left+1; i++)
        ret.push_back(answer[i]);
    
    return ret;
}