n^2 배열 자르기

작성일: 2024-11-06

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

접근 방식

n은 최대 1,000만이고, left와 right는 최대 백조까지 해당하는 문제이다.

따라서 완전 탐색을 통한 문제 해결은 불가능하고,

특정 패턴을 통한 접근으로 문제를 해결해야 한다.

이 문제는, 1x1은 1로 채우고, 2x2는 전부 2로 채우는 문제이다. (값이 없을 경우에만)

문제의 예시처럼, n=3인 경우에는,

2 3
2 3
3 3

와 같이 구성되어 있다. 이를 좌표화시키면 특정 패턴을 발견할 수 있다.

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

x와 y좌표를 비교해서 큰 값의 +1이 해당 좌표의 값임을 알 수 있다.

(1, 2) => 2>1 => 값은 2+1 = 3

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        List<Integer> list = new ArrayList<>();
        for(long i=left; i<=right; i++){
            long a = i/(long)n;
            long b = i%(long)n;
            list.add(Math.max((int)a, (int)b)+1);
        }
        return list.stream().mapToInt(a->a).toArray();
    }
}

다른 접근 방식

없음.

알게 된 점

없음.