[프로그래머스] (lv.2) n^2 배열 자르기(java)

<문제>

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

<나의 풀이>

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        ArrayList<Long> arr = new ArrayList<>();
        long leftRow, rightRow, leftCol, rightCol;	// 잘라줄 위치의 행,열
		// 1. 행, 열 초기화
        if ((left + 1) % n == 0) {
            leftRow = (left + 1) / n;
            leftCol = n;
        } else {
            leftRow = (left + 1) / n + 1;
            leftCol = (left + 1) % n;
        }

        if ((right + 1) % n == 0) {
            rightRow = (right + 1) / n;
            rightCol = n;
        } else {
            rightRow = (right + 1) / n + 1;
            rightCol = (right + 1) % n;
        }
        // 2. left~right 까지 잘랐을 때 들어올 수 넣어주기
        for (long i = leftRow; i <= rightRow; i++) {
            // 2-1) 시작점 (left)
            if (i == leftRow) {
                for (long j = leftCol; j <= n; j++) {
                    long temp = leftCol;
                    if (j <= i) {
                        arr.add(i);
                    } else arr.add(temp++);
                }
            }
            // 2-2) 중간지점 (left~right)
            else if(i>leftRow & i<rightRow){
                for (long j = 1; j <= n; j++) {
                    long temp = i;
                    if (j <= i) {
                        arr.add(i);
                    } else arr.add(++temp);
                }
            }
            // 2-3) 끝점 (right)
            else {
                for (long j = 1; j <= rightCol; j++) {
                    long temp = i;
                    if (j <= i) {
                        arr.add(i);
                    } else arr.add(++temp);
                }
            }
        }
        // 3. arrayList 를 배열로 변환
        int[] answer = arr.stream().mapToInt(Long::intValue).toArray();
        return answer;
    }
}

처음엔 문제에서 나온 애니메이션 대로 일일히 배열에 값을 채운 후 인덱스로 슬라이싱을 하려 했다.
그런데 문제 제한사항을 보니 n의 값이 1~10^7 까지였고 left, right의 값은 1~n^n 까지여서 저렇게 구현했다간 무조건 시간초과로 틀리겠거니 싶었다.

그래서 'left와 right로 자른 값만 든 배열을 만들어야겠다!' 싶어서 풀었는데 예시는 맞았지만 체점 문제에서 모조리 나가리되었다.

(심지어 메모리도 거대함..)

어떻게 하지 고민을 하다가 방법이 도저히 떠오르지않고 최대 풀이 시간인 5시간도 넘겨버려서
안타깝게도 이 문제는 풀지 못한 채 다른 사람의 풀이를 참고해서 풀었다.

<다른 사람의 풀이>

import java.util.*;
class Solution {
    public  List<Long> solution(int n, long left, long right) {
        
        List<Long> list = new ArrayList<>();
        
        for(long i=left;i<right+1;i++){
             list.add(Math.max(i/n,i%n) + 1);
        }
        return list;
    }
}

출처 : https://taehoung0102.tistory.com/93

import java.util.*;

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

<핵심 개념>

문제를 풀어낼 아이디어가 중요했던 것 같다.

행과 열의 인덱스 값 중 큰 값이 그 자리에 들어갈 값이란 사실을 알고나서 무릎을 탁 !

이 아이디어만 떠올리면 장황한 풀이 없이 간단한 풀이로 풀 수 있었다.

<피드백>

n이나 left나 right나 범위가 너무 커서 원래 짯던 코드 내에선 못푼다.
꼭 풀어내고 싶었지만 아쉽게도 내가 스스로 제한한 시간인 5시간 내에선 풀어내지 못했다.
어떻게든 풀어내고자 하면 할수도 있었겠지만 시간이 꽤 걸려서 다른 일을 못했을 것 같다.
이번주는 데브코스 코딩테스트 대비 연습을 하느라 못했던 다른 일들을 처리하느라
문제를 많이 못풀었다. 그래도 틈틈히 생각하고 또 생각해봤는데
한 가지 풀이에만 매몰되어 다른 아이디어를 떠올리지 못했던 것 같다.
분하긴 하지만 좋은 아이디어를 얻어갔고 언젠가 써먹을 날이 오면 좋겠다.
복습 하고 또 풀어봐야지.