프로그래머스 - 87390번: n^2 배열 자르기 [Java]

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

프로그래머스

1. 코드

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

2. 설명

입출력 예시의 그림을 보면 완성된 2차원 배열은 행과 열 중 가장 큰 값을 기준으로 + 1 한 값을 배열 인덱스에 저장되어 있기에 이점을 이용하여 문제를 해결할 것입니다.

long cnt = left / n * n;

cnt는 배열의 인덱스를 읽은 횟수인데 0으로 초기화를 하면 테스트 케이스 중 시간초과가 발생하는 경우가 있기에 left 값을 n으로 나눈 행부터 진행하기에 지나온 배열의 개수만큼 초기화를 해줍니다.

for(long i = left / n; i < n; i++) {
    if(cnt > right) break;
    for(long j = 0; j < n; j++) {
        if(cnt > right) break;
        if(cnt >= left)
            list.add(Math.max(i, j) + 1);
        cnt++;
    }
}

cnt의 값이 right를 넘으면 반복문을 중단시킵니다. 아니라면 cnt의 값이 left 이상일 때 행과 열의 값 중 가장 큰 값을 기준으로 + 1 한 값을 list에 저장합니다. cnt 값은 배열이 진행될 때마다 +1을 해줍니다.

3. 정리

1. 배열을 사용하여 문제를 해결하면 메모리 초과 발생
2. 반복문을 처음부터 끝까지 진행하면 시간 초과 발생
3. long 형을 사용하지 않으면 오버플로우 발생
4. 1, 2 상황을 회피하기 위해 규칙 이용

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges