[2025.02.26] n^2 배열 자르기

문제 설명

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

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i=1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   
   • 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 함수를 완성해주세요.

 

 

제한사항

• 1<=n<=10^7
• 0<=left<=right<n^2
• right-left<10^5

 

 

입출력 예

n			left	right	result	설명
3			2	5	[3, 2, 2, 3]	다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.
4			7	14	[4, 3, 3, 3, 4, 4, 4, 4]	다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타내 것입니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    for(long long index=left; index<=right; index++)
    {
        long long row=index/n; // 행 index
        long long col=index%n; // 열 index
        
        // 두 index 중 큰 값에 +1한 값 저장
        if(row>col) answer.push_back(row+1);
        else answer.push_back(col+1);
    }
    return answer;
}

2차원 배열을 만들고 나누고 난리를 쳐야할 줄 알았는데 그림을 그리면서 생각해보니 그럴 필요 없이 아주 간단하게 풀 수 있는 문제였다. 일단 2차원 배열을 다루기 위해서는 중첩 반복문을 사용해야 하는데 제한 사항을 보니 숫자의 크기가 예사롭지 않은게 그렇게 풀면 안될 것 같아 보였다.

 

입출력 예1을 이용해서 어떻게 풀어야 하는지 알아보자.

왼쪽 아래는 2차원 배열의 행, 열의 좌표를 적은 것이고, 오른쪽 아래는 2차원 배열에 들어가야하는 수를 적은 것이다.

규칙을 발견할 수 있을 것이다. 각자 행과 열의 좌표 중 큰 값에 +1을한 값을 가지고 있다는 규칙을 말이다. [0][0]의 좌표의 값은 0에 +1을 더한 1을 가진다. [2][1]의 좌표의 값은 둘 중 더 큰 수인 2에 +1을 한 값을 가진다.

또한 1차원 벡터의 인덱스를 알면 행과 열의 좌표를 알수도 있다. 이 2차원 벡터를 1차원 벡터로 만들었을 때의 인덱스 4는 2차원 벡터에서 [1][1]이다. 단순히 n을 나누어주면 되는 것이다. 인덱스에 n을 나누어준 몫이 행, 나머지가 열이 되는 것이다. index=4의 경우도 n=3을 나누어주면 몫은 1, 나머지도 1이다. 이렇게 1차원 벡터 만으로도 행열의 좌표를 구할 수 있다.

 

결론적으로 2차원 벡터를 만들 필요가 없다는 뜻이다. 새로운 벡터를 선언할 필요도 없이 처음부터 left부터 right까지의 값을 이용해 그 범위의 값들만 유추하여 answer에 넣어주면 되는것이다.

 

그래서 반복문은 한 번만으로 충분하다. left부터 right까지 반복문이 돌아가게 하고 그 index 값을 가지고 행과 열의 좌표를 알아낸다. 행과 열의 좌표를 알아내면 그 곳에 들어있던 값을 알아내는 것은 더욱 쉽다. 행과 열의 좌표 중 더 큰 값을 찾아 그 수에 1을 더한 수를 answer에 push_back하여 저장해준다.

 

 

문제 링크

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

프로그래머스