문제설명
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
- n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
- i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
- 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
- 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ n ≤ 107
- 0 ≤ left ≤ right < n2
- right - left < 105
입출력 예
n left right result
3 2 5 [3,2,2,3]
4 7 14 [4,3,3,3,4,4,4,4]
문제풀이
-
처음에는 전체적으로 만들어진 2차원 배열 모습의 결과를 1차원 배열로 나열하여 그 사이에 left ~ right까지의 값을 출력해야한다고 생각했다.
-
그 결과 시간 복잡도가 길어질뿐더러 전체적으로 다 구해야하는 코드의 불필요성이 존재하게 되었다.
-
배열의 모습을 보니 직접 전체를 구하지 않아도 2차원 배열의 열과 행의 값을 통해서 +1만하여도 같은 값이 나오는걸 확인하였다.
풀이 방법
-
left, right가 Long 타입으로 주어지기 때문에 ArrayList의 Long 타입으로 반환 타입을 변경했다.
(일반 int 형식의 Array타입은 길이를 구할 때 right-left+1을 하였으나 long타입이라서 error발생) -
행은 left~right의 현재 값 i를 n값으로 나눈 몫으로 지정
-
열은 left~right의 현재 값 i를 n값으로 나눈 나머지로 지정
-
행과 열의 Math.max값을 통해 최대값을 구하고 +1을 수행
-
answer.add(result)값을 통해 ArrayList에 값 저장
-
return
import java.util.*;
class Solution {
public List<Long> solution(int n, long left, long right) {
List<Long> answer = new ArrayList<>();
for(long i = left; i <= right; i++){
long a = i % n;
long b = i / n;
long result = Math.max(a,b) + 1;
answer.add(result);
}
return answer;
}
}배운점
- 초반에 전체적인 모습을 보고 푸는 방식을 구현해보자
- 단순히 문제를 읽고 방식을 생각해내지 말고 문제의 모습과 전체적인 결과값의 일정한 규칙을 찾아내자
- 사실 이게 2레벨인가...? 싶기도하다
문제풀이 주소
https://school.programmers.co.kr/learn/courses/30/lessons/87390
