[Programmers/Java]프로그래머스 연습문제 - n^2 배열자르기

문제링크

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

프로그래머스

문제조건

문제 설명

정수 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]

 

풀이1(실패)

행렬을 인덱스로 구분할 때, 행렬안에 들어갈 값은 row,column 인덱스값 둘 중 최댓값 + 1이다.

이를 이용해서 풀어봤다.

 

코드1 (실패)

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
                int[] answer = {};
        int size= (int) (right-left+1);
        int[] arr=new int[size];
        List<Long> ans = new ArrayList<>();
        // 행렬에 들어가는 값은 인덱스 (0,0)부터 시작이라고 쳤을 때
        // 인덱스의 최댓값 +1 이다.
        /*
            (0,0) (0,1) (0,2)
            (1,0) (1,1) (1,2)
            (2,0) (2,1) (2,2)
         */
        for(long i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int index=(int)(i*n+j);
                if(index>=left&&index<=right){
                    ans.add(Math.max(i,j)+1);
                }
            }
        }
        for(int i=0;i<ans.size();i++){
            arr[i]= Math.toIntExact(ans.get(i));
        }
        return arr;
    }
}

시간초과+실패가 나면서 실패했다. 이중for문으로 인해서 long타입에서 시간초과가 난 것 같다.

 

풀이2(성공)

더욱 간단하게 생각해봐야겠다. 시간복잡도를 줄이기 위해서 반환 사이즈는 그대로 반환할 사이즈만 선택하고,

이중 for문을 사용하지 않고 행렬을 탐색할 방법이 필요하다.

(0,0) (0,1) (0,2)              1 2 3

(1,0) (1,1) (1,2)         ->  2 2 3

(2,0) (2,1) (2,2)              3 3 3

행렬이 있을 때, 3~6번째 값만 반환한다면 3,2,2,3 이 되는데

1번 풀이에서 생각한 '행렬안에 들어갈 값은 row,column 인덱스값 둘 중 최댓값 + 1' 을 이중for문으로 인덱스를 제시하지 않고 답을 반환하는 것이다.

1번 풀이 : 이중for문으로 인덱스 설정 -> 인덱스를 바탕으로 행렬에 들어갈 값 구함 -> n번째에 저장

지금의 풀이 : n번째 값의 인덱스를 구함 -> 인덱스를 바탕으로 행렬에 들어갈 값 구함 -> n번째에 저장

만약 위 행렬에서 3번째 값을 기준으로 구한다면 row의 값은 (i+left)/n , column의 값은 (i+left)%n 이다.

 

코드2(성공)

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int size= (int) (right-left+1);
        int[] arr=new int[size];

        for(int i = 0; i < arr.length; i++){
            int row = (int)((i + left) / n) + 1; // row
            int col = (int)((i + left) % n) + 1; // column
            arr[i] = Math.max(row, col);
        }
        return arr;
    }
}