[프로그래머스 Lv.2] n^2 배열 자르기 | Java

문제 설명

문제 바로가기 클릭! 🖱️

정수 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

입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

주어진 과정대로 1차원 배열을 만드는 애니메이션

---

풀이과정

이번 문제를 풀면서, 가장 고민했던 부분은
"어떻게 배열에 번호를 넣어줄 것인가!" 그리고,
"어떻게 배열에서 번호를 꺼내올 것인가!" 였다!

1. 첫번째 시도

일단 배열을 만들어보고, 같은 숫자를 넣어 주어야 하는 곳들을 보다 보니 행과 열의 숫자 중 큰 숫자가 배열에 입력된다는 것을 알게 되었다!

이 사실을 알고난 후, 나는 n*n의 배열을 돌면서 각각의 값을 넣어 주었다!

2. 두번째 시도

그런데, 배열을 꺼내는 코드를 작성하는 과정에서
(i / n) + 1이 무조건 행의 값이 되고,
(i % n) + 1이 무조건 열의 값이 될 수 있다는 것을 알게 되었다 😂

배열에 넣는 코드를 작성할 필요 없이, 그냥 left에서부터 right까지의 값만 계산해서 넣어주면 되는 것이었다...

for(int i = 0; i < answer.length; i++){
	int row = (int)((i + left) / n) + 1;
  	int col = (int)((i + left) % n) + 1;
}    

3. 세번째 시도

행과 열의 값을 비교하여 배열에 넣어주는 과정에서
Math.max(row,col)을 사용하는 것과
row >= col ? row : col; 를 사용하는 것 중에서 고민을 하기 시작했다

두 방식 모두 정답을 맞추지만, 더 적은 시간을 써서 문제를 풀고 싶었기 때문이다.

1) Math 방식

평균 속도 : 6.35ms

2) 삼항연산자 방식

평균 속도 : 4.85ms

두 방식 모두 시도해본 결과 삼항연산자를 사용하는 것이, 복잡한 테스트를 수행할 때 더 짧은 시간 안에 정답을 찾아낼 수 있었다!

---

정답 코드

class Solution {
    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 row = (int)((i + left) / n) + 1;
            int col = (int)((i + left) % n) + 1;
            
            answer[i] = row > col ? row : col;
        }
        
        return answer;
    }
}

성능 요약

• Math 함수 방식 : 메모리: 106 MB, 시간: 4.67 ms
• 삼항연산자 방식 : 메모리: 107 MB, 시간: 3.77 ms