문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/87390
문제 설명
제한사항
알고리즘: 구현
풀이
이 문제는 arr[left], ..., arr[right]까지의 1차원 배열을 출력하는 문제다.
n은 최대 10^7이므로 n행 n열인 2차원 배열을 만들어서 값을 넣어준다면 시간 초과가 발생할 수밖에 없다. 그렇기 때문에 수식을 이용한 방법으로 답을 출력한다.
먼저 left, right를 정의할 수 있어야 한다. left, right는 2차원 배열을 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열의 index이다.
그렇기 때문에 2차원 배열일 때 행과 열을 간단한 수식으로 알아낼 수 있다.
행 -> left / n;
열 -> left % n;
그리고 right - left < 10^5 이기 때문에 left부터 right까지 순차탐색 하면서 값을 넣어주면 되는데 어떤 값을 넣어주냐? 우리는 행, 열을 모두 알고 있기 때문에 넣어줄 값 또한 간단한 비교로 알 수 있다.
문제 설명을 보면 1행 1열부터 i행 i열까지의 영역 내의 모든 빈칸을 숫자 i로 채운다.
ex)
i가 1일 때는 1행 1열부터 1행 1열까지 빈칸이 1로 채워짐
i가 2일 때는 1행 1열부터 2행 2열까지 빈칸이 2로 채워짐
i가 3일 때는 1행 1열부터 3행 3열까지 빈칸이 3으로 채워짐
....
즉 3행 4열의 값은 i가 3일 때 3행 3열까지 채우고 i가 4일 때 4행 4열까지 채우기 때문에 3행 4열을 포함한 4가 된다. -> Math.max(행, 열)
소스 코드
import java.util.*;
class Solution {
static ArrayList<Integer> answer_list = new ArrayList<>();
public int[] solution(int n, long left, long right) {
int[] answer = {};
long i = left / n;
long j = left % n;
while(i * n + j <= right) {
answer_list.add(Math.max((int) i + 1, (int) j + 1));
j += 1;
if(j == n) {
j = 0;
i += 1;
}
}
answer = new int[answer_list.size()];
for(int k=0; k<answer_list.size(); k++) answer[k] = answer_list.get(k);
return answer;
}
}