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

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
   1. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
2. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/87390?language=cpp 

프로그래머스

---

 

 

 

 

 

 

제한 사항

• 1 ≤ n ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

---

 

 

 

 

 

 

풀이

규칙을 찾아내면 간단하게 해결할 수 있는 문제이다.

우선, 이차원 행렬의 순서를 통해 행과 열의 index를 구해내는 규칙이 있다.

• 하나의 행에는 n개의 요소가 들어간다.

즉, 하나의 행에 들어가는 요소의 수를 알 수 있다.

그렇기 때문에 이차원 행렬의 k번째 수는 n개의 요소를 포함하는 i개의 행과 j개의 나머지로 표현이 가능하다.

k = n * i + j

 

그리고 문제의 조건에 맞춰 채워진 이차원 행렬은 신기한 규칙을 갖는다.

1(0,0)	2(0,1)	3(0,2)
2(1,0)	2(1,1)	3(1,2)
3(2,0)	3(2,1)	3(2,2)

i, j 중 큰 수를 채택하여 1을 더한 수가 요소가 된다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;

    int leftI = left/n;
    int leftJ = left%n;
    
    int rightI = right/n;
    int rightJ = right%n;
    
    // 0,2 ~ 1,2
    
    for(int i = leftI; i <= rightI; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == leftI && j < leftJ) continue;
            if(i == rightI && j > rightJ) break;
            
            answer.push_back(max(i+1, j+1));
        }
    }

    
    return answer;
}

---