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

문제 링크

문제 설명

정수 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
• 0 ≤ left ≤ right < n2
• right - left < 105

---

입출력 예

---

입출력 예 설명

입출력 예 #1

입출력 예 #2

---

2023.04.11

첫 번째 풀이

• 빈 배열을 만들어서 1번부터 차례대로 자신의 알맞은 배열 번호에 넣어주기

public int[] solution(int n, long left, long right) {
    int[] answer = new int[(int) (right - left + 1)];

    //빈 배열 만들기
    int[] temp = new int[n*n];
    
    //각 배열의 숫자를 넣어주기 위해서
    int cnt = n;

    //숫자 넣기
    for (int i = 0; i < n; i++) {
        //n = 3일 경우, [1, 0, 2, 2, 0, 3, 3, 3] 이런식으로 숫자를 넣어주는 반복문
        for (int j = i * n; j <= (i * n) + i; j++) {
            temp[j] = i + 1;
        }
        //n = 3일 경우, [1, 2, 2, 2, 3, 3, 3, 3] 빈 곳에 각 숫자를 넣어주는 반복문
        for (int j = n; j <= (i * n); j += n) {
            temp[j - cnt] = i + 1;
        }
        //배열의 자리를 맞추기 위해서
        cnt--;
    }

    int num = (int) left;

    //left부터 right 까지의 배열을 가져오기
    for (int i = 0; i < answer.length; i++) {
        answer[i] = temp[num];
        num++;
    }

    return answer;
}

결과

런타임 에러와 메모리 초과 발생

• 모든 데이터를 전부 구하고 하는 과정에서 에러가 발생한다고 생각

---

두 번째 풀이

• 배열을 좌표라 생각하고 풀기

  예를 들어서 n = 3일 경우,
  (1, 1) (1, 2) (1, 3)
  (2, 1) (2, 2) (2, 3)
  (3, 1) (3, 2) (3, 3)
  라고 가정 하였을 때, 앞에 Math.max 를 사용하면 둘 중 더 높은 값을 값으로 가지게 된다.

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 x = (int) (left / n + 1);
        int y = (int) (left % n + 1);
        left++;
        answer[i] = Math.max(x, y);
    }

    return answer;
}

결과

통과