[프로그래머스,java] Levle2: n^2배열 자르기

 

문제분석

 

문제를 읽어보니 꽤나 친절한 문제다!

 

1. n^2 크기의 배열을 만들고

2. i행 i열 까지 i로 숫자를 세우고

3. 행 마다 모두 잘라서 새로운 1차원 배열을 만들고

4. left~right 사이에 있는 숫자들을 뽑아오면 된다!

 

아주 친절하게 애니메이션(함정)까지 준비해놨다

 

만약,  문제설명 1~4번 과, 애니메이션이 설명하는 영상처럼 구현한다면 

 

당신은 함정에 빠졋습니다.  (필자도 당함)

 

 

그대로 구현하면 안되는이유 

 

1.메모리초과 -> n이 10^7 이면, n^2 이 int범위를 넘어가서 Overflow

 

2.String, list ,StringBuilder는 Long타입(left,right)를 지원하지않음

 

 

따라서, 다시한번 생각을 정리해서 새로운 접근을 시도해봐야합니다.

 

 

 

(2,3) =3  (4,1)=4

 

이렇게보니, 각 열 각 행 마다 일정한 규칙이존재합니다.

 

네, 바로  Max(행,열) 의 idx값이 그 자리의 값입니다.

 

그렇다면, 우리가 뽑고싶은 숫자가, Left~Right 범위의 숫자니,

 

Left에서 Right까지 순회하면서 Max(행,열)을 반환해주면 되겟죠?

 

문제풀이

 

import java.util.*;
class Solution {
    public  List<Long> solution(int n, long left, long right) {
        
        List<Long> list = new ArrayList<>();
        
        for(long i=left;i<right+1;i++){
             list.add(Math.max(i/n,i%n) + 1);
        }
        
        return list;
    }
}