프로그래머스 n^2 배열 자르기 자바 월간 코드 챌린지 시즌3

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

코딩테스트 연습 - n^2 배열 자르기

 

안녕하세요!

오늘은 프로그래머스 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 ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

---

 

3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

 

---

이 문제는 그냥 단순하게 이중배열로 구현 후 자르거나 1차원 배열을 쭉 나열한 다음 자르거나 등 

2중 반복문을 쓰게 될 경우 시간초과가 뜨거나 혹은 메모리 초과 가 나옵니다 

제가 원래 생각했던 방식은 0번째 인덱스 부터 right 까지 쭉 나열한다음 

left 부터 right 까지를 잘라서 return 하면 반복문 한번만 쓰게 할 수 있어서 될 줄 알았는대 이렇게 하면 메모리 초과 가 나왔습니다 ㅠㅠ 

 

이 문제를 풀기 위해서는 규칙을 찾아내서 규칙을 이용해서 해답을 구해야합니다 

 

이 배열에서 left 2 부터 right 5를 짜르려고 합니다 

근대 가만히 보면 규칙이 있습니다 그 규칙은 각 행과 열의 최댓값이 들어가있습니다 

이게 무슨말이냐 하면 

(2,2)는 2이고 

(1,3)은 3입니다

(2,1)은 2

(3,1)은 3

즉 행과 열의 최댓값이 행열에 원소값이라는것 을 알수 있습니다

우린 이 규칙을 이용하면 메모리 초과 , 시간 초과  이 두 문제를 해결할 수 있습니다

 

이 문제는 알고리즘이 어렵다긴 보다는 누가 빠르게 규칙을 찾아 낼 수 있는냐가 중요한 문제인거 같습니다

import java.util.Arrays;

class Solution {
    public int[] solution(int n, long left, long right) {

        int[] answer = new int[(int) ((right-left)+1)];
        int index = 0;
        for(long i = left ; i<=right;i++){
            answer[index++] = (int) Math.max((i/n)+1 , i%n+1);
        }
        return answer;
    }

    public static void main(String [] args){

        System.out.println(Arrays.toString(new Solution().solution(3, 2, 5)));
    }
}