[프로그래머스/JAVA] 코딩테스트 연습 > 월간 코드 챌린지 시즌3 > n^2 배열 자르기 (by 다알쥐AI)

 

[ n^2 배열 자르기] 코딩테스트 연습 > 월간 코드 챌린지 시즌3 > n^2 배열 자르기

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 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

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

입출력 예 #2

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

---

[간단설명]

2차원 배열을 만들어서, n^2 으로 값을 채우고, 1차원 배열로 변환해서, left ~ right 까지 배열 자르기

 

[접근방법]

1. 1차원 배열의 사이즈를 구한다.

2. 행(row), 열(col)의 값을 구한다.

3. 행이 열보다 크면 행(row) 값을, 행이 열보다 작으면 열(col) 값을 넣는다.

4. left ~ right 까지 반복한다.

5. 정답 배열을 리턴한다.

 

[주의사항]

1. long형을 int형 변환시 주의

ㄴ (int)i/n 이면 i를 먼저 형변환 시키니, 괄호(i/n)로 계산한 뒤 형변환(int) 시켜야 한다.

2. 문제 그대로 2차원 배열을 만들시 메모리 초과 오류가 난다

ㄴ ex) arr[n][n]

3. 문제 그대로 2중 for문을 구현하게 되면, 시간 초과 오류가 난다.

ㄴ left ~ right 범위 만큼만 반복하고, 수식을 구해서 접근하자

4. n^2 값은, 1행 3열도 3, 3행 1열도 3이다.

ㄴ max 값으로 둘 중 큰 값을 구하던지, 조건문 으로 처리하자(여기에서는 조건문 처리)

 

[소스공개]

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        // 배열 사이즈
        long size = right-left+1;
        // 정답 배열
        int[] answer = new int[(int)size];
        // 정답 인덱스
        int idx=0;
        // left ~ right 까지 반복
        for(long i=left; i<=right; i++){
            // 열, 행
            // ex) i=2, n=3 -> 1행 3열
            int row = (int)(i/n)+1;
            int col = (int)(i%n)+1;

            // 행이 열보다 작으면
            // ex) 1행 3열, col = 3
            if(row<col){
                answer[idx++] = col;    
            // 행이 열보다 크면
            // ex) 3행 1열, row = 3
            }else{
                answer[idx++] = row;    
            }
            
        }
       
        return answer;
    }
}

 

[실행결과]