[프로그래머스] n^2 배열 자르기 (JAVA)

프로그래머스

 

풀이

 

1. 아이디어

• n의 최대 크기가 10^7이기 때문에 2차원 배열이 아닌 1차원 배열로 해결해야겠다는 생각을 했다.
• 그러던 중 i 번째에 위치한 숫자는 몫과 나머지 중에 더 큰 수+1 이라는 걸 알게 됐다.

 

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)

 

예를들어 n이 3인 배열이라고 한다면, 각 배열마다의 행(몫)과 열(나머지)는 이렇다.

1	2	3
2	2	3
3	3	3

 

(2,1)의 경우 들어가야 하는 수가 3이다. 2와 1중에 더 큰 숫자인 2에 1을 더해주면 3이 나온다.

 

2. 헤맨 부분

• long / int처럼 자료형이 다른 변수를 사칙연산으로 계산할 때, 형변환을 해줘야 했는데 여기서 문제가 발생했다.

long i = 99999999999;
int n = 10000000;

int mod = i / n; // 이 경우 에러가 발생

int mod = (int) i / n; // 이 경우 9999가 아닌 121로 몫이 나왔다.

long mod = i / n;
list.add((int) mod+1); // list에 넣어줄 때 int로 형변환하니 9999가 나옴.

 

• 형변환을 해야겠다고 생각한 뒤 mod에 나누면서 (int)로 형변환을 하니 잘못된 답이 나왔다.
• 그래서 list에 넣어줄 때 (int)로 형변환을 하니 제대로 된 값이 나왔다!
  (원리가 뭔지에 대해서는 조금 더 공부해봐야겠음)

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    public ArrayList<Integer> solution(int n, long left, long right) {
        ArrayList<Integer> list = new ArrayList<>();
        for(long i = left; i <= right; i++){
            long quo = i / n;
            long mod = i % n;
            list.add(Math.max((int)quo+1, (int)mod+1));
        }

        return list;
    }
}