[ 프로그래머스 JAVA ] n의 제곱 배열 자르기

문제 출처

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

프로그래머스

걸린 시간

11:47 ~ 12:31 // 소요 시간 45분

피드백

확실히 이런 문제는 예시를 주욱 늘여트려 놓고 뭔가 반복되는 것을 찾는게 빠른 것 같다.

문제

정수 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]
4	7	14	[4,3,3,3,4,4,4,4]

수도코드

n = 1

1

n = 2

1222

n= 3

123223333

n=4

0123456789…  <- answer 인덱스 

0000111122223333 <- 몫의 배열 

0123012301230123 <- 나머지의 배열 

1234223433344444 < - 실제 1행 , 2행 , 3행 쭉 길게 늘여트려놓은 배열

 

나머지가 몫+1 보다 작으면 배열의 값은 몫+1

아니면 나머지+1

 

소스 코드 ( 자세한 내용 주석 참고 )

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left + 1)];
        
        // 이중배열 그대로 쓰기엔 사이즈가 좀 큼 
        // 행과 열을 구해서 배열을 만들자. 
        int answerIdx = 0;
        
        // case를 주욱 늘여트려보니 
        // 나머지가 몫+ 1 보다 작으면 배열의 값은 몫 + 1
        // 아니면 나머지 + 1 이더라~
        for( long i = left ; i <= right ; i ++ ){
            if( (i % n) < (i / n) + 1 ){
                answer[answerIdx] = (int)(i / n) + 1;
            }
            else{
                answer[answerIdx] = (int)(i % n)+1;
            }
            answerIdx++;
        }
        
        return answer;
    }
}