프로그래머스 n^2 배열 자르기 Java 자바 문제풀이

문제설명과 예제

문제가 다음과 같이 주어져있다.

n x n의 정사각형 2차원 배열에서 순차적으로 값을 채워나가면 된다.
row와 column으로 따졌을 때 다음과 같이 값을 채울 수 있다.

1) r == c 일 때
처음 1을 예를 들자면 r과 c값이 같은 자리 (0,0)에 1이 자리하고있다.
그 다음 2를 보면 똑같이 r과 c값이 같은 자리 (1,1)에 2가 자리하고있다.
3, 4도 마찬가지다.
즉 순차적으로 나갈수록 좌측 상단부터 우측 하단까지 대각선을 그었을 때 r과 c가 일치하는 자리마다 해당 숫자가 위치한다. (물론 좌표는 0,0 이지만 값은 1부터 들어가기 때문에 +1로 생각)

2) (r,c)에서 (r == i) 또는 (c == i) 일 때
예제를 살펴보면 r 또는 c의 값이 현재 순환하고 있는 값과 같을 경우 해당 값을 입력하고 있다.
(0,1) 과 (1,0) 그리고 (1,1)에 2가 입력된 것을 볼 수 있다.
(1,2) 와 (2,1) 그리고 (2,2)에 3이 입력된 것을 볼 수 있다.
따라서 행과 열에 해당하는 값과 같은 행 또는 열일 경우에는 값을 입력 해준다.

이렇게 되면 기본적으로 자리마다 채우는 값의 규칙을 알 수 있게 되었다.
1번과 2번을 합치면 결국 행과 열에 현재 순환하는 값과 같은 값일 경우 입력 해주고 반복 해주면 된다.

그런데 이때 중요한 것이 있다. 2번에서 (1,0) 에도 1이 있고 (1,2)에도 각각 1이 있지만 입력된 값은 각각 2와 3이다. 어떻게 된걸까?
바로 두 값중에 큰 값이 입력된다는 점이다.

즉, (1,2)에서는 둘 중에 큰 값에 +1이 된 3이 입력되고 2는 제외된다.
이와 같은 규칙으로 찾아내면 된다.

하지만 문제에서 주어진 것처럼 2차 배열을 작성하고 그것을 이어 붙여서 다시 1차배열로 만들어 잘라낸다면 n이 10^7까지 주어졌을 때 n^2이 int범위인 10^9 를 넘어간다.

따라서 효율성 테스트를 통과하지 못하거나 최대값이 주어졌을 때 제한조건을 만족하지 못한다.

그렇다면 어떻게 해야할까?

위에서 규칙을 봤듯이 (r,c) 에서 둘중에 최댓값을 구해주면 된다.

class Solution {
  public int[] solution(int n, long left, long right) {
     int answer = new int[(left-right) + 1]; //시작점부터 포함해야 하므로 +1 크기로 선언

     int idx = 0; //list로 변형해서 처리하면 필요 없음
     for(int i = left; i<right+1; i++){
         answer[idx] = (Math.max(i/n, i%n) + 1);
         idx++;
     }
}
 n = 3;
 left = 2;
 right = 5; 
 1, 

크나큰 문제가 있었다. 주어진 left와 right의 long 값 때문에 실행 결과가 더러워졌다.
그래서 반환 값 자체를 List<Long'>으로 바꿔버렸다.

    public List<Long> solution(int n, long left, long right) {
        List<Long> answer = new ArrayList<>();

        for (long i = left; i < right + 1; i++) {
            answer.add(Math.max(i / n, i % n) + 1);
        }
        return answer;
    }

결과는 통과!