[프로그래머스] n^2 배열 자르기(Java 자바)

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

코딩테스트 연습 - n^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 함수를 완성해주세요.

---

제한사항

• 1 ≤ n ≤ 10^7
• 0 ≤ left ≤ right < n2
• 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]

---

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left + 1)];
        
        
        long leftRow = left / n;
        long leftCol = left - (n * leftRow);
        
        long rightRow = right / n;
        long rightCol = right - (n * rightRow);
        

        if(leftRow != rightRow){
            int idx = 0;
            for(int i = (int)leftCol; i < n; i++){
                if(i < leftRow+1){
                    answer[idx] = (int)leftRow+1;
                }else{
                    answer[idx] = i + 1;
                }
                idx++;
            }
            
            for(int i = 0; i < rightRow - leftRow -1; i++){
                int row = (int)leftRow+i+1;
                for(int j = 0; j < n; j++){
                    if(j < row + 1){
                        answer[idx] = row + 1;
                    }else{
                        answer[idx] = j + 1;
                    }
                    idx++;
                }
            }
            
            for(int i = 0; i < rightCol+1; i++){
                if(i < rightRow+1){
                    answer[idx] = (int)rightRow+1;
                }else{
                    answer[idx] = i + 1;
                }
                idx++;
            }
            
        }else{
            int idx = 0;
            for(int i = (int)leftCol; i < rightCol+1; i++){
                if(i < leftRow+1){
                    answer[idx] = (int)leftRow+1;
                }else{
                    answer[idx] = i + 1;
                }
                idx++;
            }
        }
        

        return answer;
    }
}

핵심 코드, 푸는법:

우선 문제 설명대로 풀었지만 제한사항의 값 때문에 시간초과와 메모리 초과가 났다.

 

이를 개선하기위해 left의 좌표와 right의 좌표를 직접 구하였다.

 

left, right의 좌표 계산 후 left좌표에서 right좌표까지의 값을 구해주는 단순 좌표, 값 계산문제다. 

 

좌표계산 문제는 정말 헷갈린다...

(복잡하게 풀었지만 더 쉬운 방법이 있을 것이다...)

 

 

반복되는 코드 함수화...

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left + 1)];
        
        
        long leftRow = left / n;
        long leftCol = left - (n * leftRow);
        
        long rightRow = right / n;
        long rightCol = right - (n * rightRow);
        

        if(leftRow != rightRow){
            int idx = 0;
            idx = fuc((int)leftCol, n, idx, answer, (int)leftRow);
            
            for(int i = 0; i < rightRow - leftRow -1; i++){
                int row = (int)leftRow+i+1;
                idx = fuc(0, n, idx, answer, row);
            }
            idx = fuc(0, (int)rightCol+1, idx, answer, (int)rightRow);
            
        }else{
            int idx = 0;
            idx = fuc((int)leftCol, (int)rightCol+1, idx, answer, (int)leftRow);

        }
        

        return answer;
    }
    
    public int fuc(int start, int end, int idx, int[] answer, int row){
        for(int i = start; i < end; i++){
            if(i < row+1){
                answer[idx] = row+1;
            }else{
                answer[idx] = i + 1;
            }
            idx++;
        }
        return idx;
    }
}