[프로그래머스 87390] Level2 n^2배열 자르기

문제 URL

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

프로그래머스

 

문제풀이 Key Point

• i행 j열의 값은 i와 j중 더 큰 값에 +1을 한 것이다.
  (0행 0열부터 시작한다고 가정)
• n x n 배열을 행 기준으로 잘라 이어 붙였을 때, 각 인덱스는 [i / n][i % n]이 된다.
• 예를들어, 3 x 3 배열에서 인덱스 2의 위치를 찾는 다면 [2 / 3 = 0][2 % 3 = 2]가 되므로 0행2열의 값이 된다.
  7의 위치를 찾는 다면 [7 / 3 = 2][7 % 3 = 1]가 되므로 2행1열의 값이 된다.

 

처음 구현시 메모리 초과 발생

가로의 인덱스를 계산을 통해 n x n에서의 행과 열을 구하는 것을 생각해내기 전이었다.

int[][] map = new map[n][n];을 생성해서 모든 맵에 값을 넣어주면서 발생한 메모리 초과였다.

이후 문제풀이 Key Point에 적어둔 내용을 생각해내게 되며 통과할 수 있었다.

 

Java 문제풀이

import java.util.List;
import java.util.ArrayList;
 
class Solution {
    public int[] solution(int n, long left, long right) {
        int gap = (int) (right - left);
        int[] answer = new int[gap + 1];
        int index = 0;
        for (long i = left; i <= right; i++) {
            int x = (int) (i / n);
            int y = (int) (i % n);
            
            answer[index++] = x > y ? x + 1 : y + 1;
        }
        
        return answer;
    }
}