[문제풀이] 프로그래머스 월간 코드 챌린지 <n^2 배열 자르기> 자바 풀이

👉 문제

문제 설명
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

입출력 예

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.stream.IntStream;
import java.util.stream.Stream;
class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = {};
        int[][] board = new int[n][n];
        for(int i = 1; i <=n; i++){
            if(board[i][i] == null ){
                for(int j = 1; j <= i; j++) {
                    board[i][j] = i;
                    board[j][i] = i;
                }
            }
        }
        
        int[] arr = Stream.of(board)
            .flatMapToInt(IntStream::of)
            .toArray();
        
        int start = (int) left;
        int end = (int) right;
        
        for(int i = start; i <=end; i++) {
            answer[i]=arr[i];
        }
        
        return answer;
    }
}

단순하게 어쩌면 무식하게(;;) 2d 배열을 board라는 이름으로 만들어 수를 다 입력하고, 1차원 배열로 바꾸고, 거기서 left~right 값을 가져오는 방식을 생각했다. 거의 30줄 가까이 코드를 쓰고 에러도 많이 나서 이 문제가 이렇게까지 긴 코드를 필요로 하는 문제인가 의문이 들었다.

• 통과된 코드

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left) + 1];
       //정답은 right에서 left를 빼고 1을 더해준 길이다.
        
        for(int i = 0; i < answer.length; i++){
            int row = (int)((i + left) / n) + 1; // 몫 +1
            int col = (int)((i + left) % n) + 1; // 나머지 +1
            answer[i] = Math.max(row, col);
        }
        
        return answer;
    }
}

그러다 찾은 규칙은,
1 2 3 4 5
2 2 3 4 5
3 3 3 4 5
4 4 4 4 5
5 5 5 5 5
이런 보드가 있다고 했을 때, 어떤 숫자 x의 좌표 (행, 열)은 x에 도달할 때까지 쭉 x이다가, 이후에는 (행, 열) 둘 중 큰 값이 보드에 입력된다는 것이었다. 예를 들어 x=3이면 (3,3) 좌표까지는 x번째 행과 x번째 열의 값이 3이다. 그러다 좌표가 (3,4)가 되면 값은 4고, (3,5)가 되면 값은 5다.

이 규칙에 따르면 주어진 left부터 right까지의 수는 좌표의 행과 열을 구하여 둘 중 큰 값을 넣으면 된다. 규칙을 찾아서 푸니 코드 길이가 절반 줄었을 뿐만 아니라, 시간복잡도도 확연히 줄었다!