[프로그래머스][Lv.2][JAVA][월간 코드 챌린지 시즌3]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

---

입출력 예

 

입출력 예 설명

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

 

---

 

분석

1. 문제에서 제시된 대로 순차적으로 2차원 배열, 1차원 배열, 그걸 조건대로 자른 배열로 만들어가도 된다.
2. 그런데 좀 더 빠르고 효율적으로 정답을 도출하기 위해서는 규칙성을 찾아서 새로운 방법으로 진행해야 할 것 같다. n이 최대 10의 7승까지 주어진다는데, 이걸 모두 구성할 수는 없어! 
3. 예를 들어, 입출력 예 (1) 과 같이 n = 3이라고 해보자.
4. 그림으로도 설명되어 있지만, 2차원 배열은 아래와 같이 구성된다.
   1 2 3
   2 2 3
   3 3 3 
   즉, 2차원 배열 arr 이 있다고 할 때 arr[i][j] 의 값은 [i, j 중 더 큰 값 +1]이 된다.
5. 그리고 이 이차원 배열 arr을 1차원 배열로 재구성한 arr2가 있을 때 아래와 같이 구성된다.
   인덱스 : 0 1 2 | 3 4 5 | 6 7 8
   요소값 : 1 2 3 | 2 2 3 | 3 3 3 
   arr2의 인덱스 x를 2차원 배열이었을 때의 인덱스로 변환하면 [x/3][x%3] 이 된다.
   이걸 이용하면 2차원 배열을 만들어서 1차원으로 옮기는 게 아니라, 1차원 배열에서 바로 그 값을 구할 수 있다. 
6. 그리고 이 arr2를 다시 인덱스 left 부터 right 까지 자른 것이 최종적으로 반환해야 할 return 값이 되는데, 이건 arr2에서 Arrays.copyOfRange(arr2, left, right+1) 을 사용해서 만들 수도 있지만, 우리가 arr2에서의 인덱스를 알고 있고, 그 인덱스가 가져야 할 값을 알고 있다면 사실 arr2도 만들 필요가 없고 바로 return해야할 배열에서부터 시작해도 되지 않을까?
7. 예를 들어, arr2 를 위에처럼 구해놓고 left는 3, right는 5까지로 주어졌으니 잘라낸다고 쳐보자.
   원래 인덱스 : 2 3 4 5 
   자른 인덱스 : 0 1 2 3
   인덱스의 값 : 3 2 2 3
   이렇게 구성되는데, right는 사실상 자른 배열의 총 길이를 구하는 용도이고 (right - left + 1), 중요한 건 left가 된다.
8. 반환해야 할 int[]는 (right-left+1)의 길이를 가진 배열 arr3이 되고, 그 배열 안에서 인덱스 y인 요소의 값은 아래와 같다.
   arr3[y] = max((y+left)/3+1, (y+left)%3+1)
9. 그러면 우리는 for(int i = 0; i < (right-left-1); i++) 이라는 루프문을 통해 이 배열을 모두 완성할 수 있다. arr1과 arr2가 없이 arr3을 바로 구성해서 제출하면 끝. 

 

 

 

---

 

피드백

1. 나는 더 큰 수의 비교를 위해 Math.max 를 이용했는데, int로 캐스팅하는 부분이라던가 메서드를 이용하는 게 if-else로 비교하는 것보다 성능적으로 불리할 수 있다는 분석을 받았다(챗지에게). 음, 코드를 더 간결하게 짠 것처럼 보이고 싶었던 허세의 무의식이 반영된 게 아닌가 하는 반성... 필요할 땐 안 쓰고 필요없을 땐 쓰는 코드잡지식. 
2. 그래도 규칙 도출까지는 잘 한 것 같다! 도출까지 좀 오래 걸리긴 했지만... 앞으론 문제풀 땐 좀 더 집중하자. 

 

 

 

---

 

답안

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

 

 

 

---

 

다른 사람의 답안

// 오랜만이군, 스트림...

import java.util.Arrays;
import java.util.stream.LongStream;

class Solution {
    public int[] solution(int n, long left, long right) {
        return LongStream.rangeClosed(left, right).mapToInt(value -> (int) (Math.max(value / n, value % n) + 1)).toArray();
    }
}

 

 

// List를 이용한 코드.

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        List<Integer> ansList = new ArrayList<>();
        int leftInt = (int)left;
        int rightInt = (int)right;

        for(long i = left; i <= right; i++){
            if(i / n <= i % n)
                ansList.add((int)(i % n) + 1);
            else
                ansList.add((int)(i / n) + 1);
        }

        int[] answer = new int[ansList.size()];

        for(int i = 0; i < answer.length; i++)
            answer[i] = ansList.get(i);

        return answer;
    }
}

 

 

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        List<Integer> ansList = new ArrayList<>();
        int leftInt = (int)left;
        int rightInt = (int)right;

        for(long i = left; i <= right; i++){
            if(i / n <= i % n)
                ansList.add((int)(i % n) + 1);
            else
                ansList.add((int)(i / n) + 1);
        }

        int[] answer = new int[ansList.size()];

        for(int i = 0; i < answer.length; i++)
            answer[i] = ansList.get(i);

        return answer;
    }
}

 

 

---

 

🔗링크

프로그래머스