링크

문제 링크

문제 설명

정수 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 함수를 완성해주세요.

제한 사항

1 ≤ n ≤ 107 (10의 7제곱임)
0 ≤ left ≤ right < n2
right - left < 105

입출력 예

입출력 예 설명

문제 설명을 애니메이션으로 되어있어서 문제 링크 참조 바람!

풀이

1. 문제의 규칙을 찾기 위해 수학적으로 접근하였다.
2. 2차원 배열이 있다고 가정하고 예제 2번은 (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) 순으로 answer 배열에 들어가면 된다.
3. 초기 (1,3)을 (x1,y1)으로, 목표치인 (3,2)를 (x2,y2)로 잡고 반복문을 구현하였다. (x1,y1,x2,y2 구하는 식은 코드에 있음)

이 문제의 제한사항을 보자마자 2차원 배열을 선언하면 메모리초과가 뜨겠구나 라는 생각이 들었지만 한번 선언해보았다. 바로 메모리 초과가 떴다!

바로 후퇴한 후, 잠깐 생각해보니 메모리를 right - left + 1만큼 쓰고 문제를 풀기 위해서는 시간복잡도 또한 O(right-left+1)만에 푸는게 상식적이라는 생각이 들었다.

그리고 바로 구현을 시작하였다!

반복문을 구현하는데 많은 애를 먹을 줄 알았는데.. 솔직히 첫 제출만에 맞을줄은 몰랐다.

나는 디버깅을 통해서 이번껀 정답이 확실하다는 느낌이 들 때 코드를 좀 간소화하고 제출하는 타입이다!

그래서 코드가 조금 지저분하다...

우선 코드에 저렇게 자료형 캐스팅을 해놓지 않으면 자꾸 long에서 int로 형변환 오류가 뜬다..

일단 larger함수를 선언하게 된 배경은 풀이 2번처럼 좌표를 저렇게 놓고보니 좌표값 둘 중에 큰 값 +1 한 값이 실제 2차원배열에서 그 좌표의 값이더라. 그래서 굳이 larger를 선언하였다..!

솔직히 풀이가 깔끔하진 않은 것 같다. 그러나 시간복잡도는 알차게 쓴듯..?

코드

class Solution {
    public int larger(int a, int b){
        return a > b ? a : b;
    }
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left + 1)];
        int x1 = (int)(left / n); 
        int y1 = (int)(left % n);
        int x2 = (int)(right / n);
        int y2 = (int)(right % n);
        int index = 0;
        for(; x1 <= x2 && index < (int)(right - left + 1); y1 = (y1 + 1) % n) {
            answer[index++] = larger(x1,y1) + 1;
            if(y1 > (y1 + 1) % n) x1++;  
        }
        return answer;
    }
}