[자바] 프로그래머스 - n^2 배열 자르기 (Lv2, Java)

문제 : Programmers-n^2 배열 자르기

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

 

필요 알고리즘 개념

• 구현, 수학
  
  • 태그가 상당히 애매하긴한데, 그냥 단순 구현문제인 것 같다.

 

1. 문제에서는 2차원 배열을 만들고나서 1차원배열로 만들고, left부터 right까지를 출력하라고 했으나, 애초에 n의 최대값이 10^7이므로 2차원 배열을 만드는 순간 물리적으로 O(10^14)가 필요해서 무조건 시간초과이다. (대강 O(10^9)을 1초로 잡으면 되므로 10만초임)

2. 마찬가지로, 1차원 배열로 바꾸는것도 O(10^14)이므로 하면 안됨.

3. 그럼 남은건 left부터 right까지에 대해 right - left < 10^5 이므로 left부터 right까지 각 O(1)로 원하는 값을 찾을 수 있어야 한다.

 

  결론적으로 특정 (r, c) 위치의 값을 O(1)로 구할 수 있으면 된다. 공책에 좀 그려보면 규칙성을 찾을 수 있는데, max(r, c)+1이 해당 칸의 값이 된다. 그렇다면 left부터 right까지 1차원 배열의 인덱스값을 가지고 원래의 (r, c) 위치만 찾을 수 있다면 답을 구할 수 있다. 이건 1차원 배열에서의 인덱스가 x라고 할 때, x/n이 r값이고 x%n이 c값이다.

 

  따라서 left부터 right까지 각각의 인덱스값에 대해 max(x/n, x%n)+1 을 answer배열에 기입해서 리턴해주면 된다. 생각해내는 과정이 레벨 2는 아닌 것 같고, 개인적으론 레벨 3으로 생각된다.

 

 

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    private int getNum(long idx, int n) {
        long r = idx / n;
        long c = idx % n;
        return (int)((r>c?r:c)+1);
    }
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int) (right - left + 1)];
        for (long i = left; i <= right; i++) {
            answer[(int)(i-left)] = getNum(i, n);
        }
        return answer;
    }
}