문제 87390. n^2 배열 자르기

문제 링크

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

프로그래머스

 

 

난이도 : Lv.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 함수를 완성해주세요.

 

문제 예시

 

 

입력

• 정수 n, left, right

입력 제한

• 1 ≤ n ≤ 10^7
• 0 ≤ left ≤ right < n^2
• right - left < 105

입력 예제

// input(params)
3 2 5 // n left right

// ans
[3,2,2,3]

 

풀이 방식

해당 문제의 결과를 내는 방식은 어렵지 않지만, n의 크기가 최대 10^7이기 때문에 O(N^2)의 연산이 들어가는 코드가 하나라도 있으면 안된다. 따라서 이 문제에 표현되는 정사각형 모양의 2차원 배열을 만든 다음 값을 가져오는 방법은 메모리든, 시간이든 초과가 나버리게 된다.

 

그럼 어떻게 풀어야 하는가?

answer에 저장될 내용을 계산해서 바로 넣어야한다. 만들고자하는 2차원 배열의 패턴을 보면 각 값은 행 또는 열의 index+1의 값 중 큰 값을 가지는 것을 알 수 있다. 이를 이용해 answer에 저장하고 반환하면 정답이 된다.

정답 코드 

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

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    answer.resize(right-left+1);
    
    for(long long i = left; i <= right; i++){
        answer[i - left] = max(i/n, i%n) + 1;
    }
    
    return answer;
}