[99클럽 코테 스터디 1일차 TIL] 프로그래머스 - n^2 배열 자르기

99클럽 코테 스터디 1일차 TIL 입니다.

[level 2] n^2 배열 자르기 - 87390

문제 링크

성능 요약

메모리: 85.9 MB, 시간: 7.41 ms

문제 설명

정수 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 ≤ 10^7

• 0 ≤ left ≤ right < n^2

• right - left < 10^5

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

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

ex1

---

의식의 흐름

처음엔 어떻게든 2차원 배열을 만들려고 했는데 예제의 그림처럼 만들기가 어려웠다.

그러고보니 반환 값은 1차원 배열이니까 굳이 2차원 배열을 만들 필요가 있을까? 란 생각이 들어서 한번에 1차원 배열을 만들기로 결정했다.

만들려고 보니 어차피 2차원 배열을 만들 줄 알아야 했다. 노트에 적어놓고 뚫어지게 쳐다보니 규칙이 보였다.

• 1행 1열 - 1

• 1행 2열 - 2

• 2행 2열 - 2

• 2행 3열 - 3

• 3행 1열 - 3

행과 열 중 큰 값이 해당 위치의 값이 된다. Math.max() 함수를 이용하면 되겠다. 이제 한번에 1차원 배열만 만들면 된다.

일단 반환해야할 배열 크기는 right - left + 1 이란걸 알 수 있다. 문제 제한 사항에서도 친절하게 right - left 는 10^5 미만 즉, 정수형 범위 안에 있다고 알려준다. 괜히 알려주는게 아니라고 생각했다.

그리고 예제 애니메이션에서 보여주는 것처럼 1차원 배열에서 left 인덱스 위치부터 right 인덱스 위치까지 값만 구해서 반환하면 끝이다.

left 인덱스 위치의 행과 열 값만 알면 값은 바로 알 수 있다. 여기서 막혀서 다른 분들의 문제 풀이를 참고하여 문제를 해결했다. 아래는 풀이 코드이다.

class Solution {
    public int[] solution(int n, long left, long right) {
        int len = (int) (right - left);
        int[] answer = new int[len + 1];

        int idx = 0;
        for (long i = left; i <= right; i++) {
            answer[idx++] = (int) Math.max(i/n, i%n) + 1;
        }
        
        return answer;
    }
}

코드를 보면 행 값은 i/n 이고 열 값은 i%n 인걸 알 수 있다.

돌아보기

위의 행 값과 열 값의 규칙을 찾게 되는 과정이 이해되지 않아 ChatGPT 에게 물어봤다. 답변을 통해 알게된 건 1차원 배열의 인덱스 위치와 2차원 배열 좌표 사이의 관계성을 생각해야 했다는 것이다.

예를 들어 3-3 크기의 2차원 배열을 만든다면 1차원 배열의 인덱스 값과 2차원 배열의 좌표 값은 아래와 같을 것이다.

1차원 배열의 인덱스 값	2차원 배열의 좌표 값
0	(0, 0)
1	(0, 1)
2	(0, 2)
3	(1, 0)
4	(1, 1)
5	(1, 2)
6	(2, 0)
7	(2, 1)
8	(2, 2)

좌표 값이 특정 규칙에 따라서 2차원 배열의 크기만큼 반복되는걸 볼 수 있다. 0번째와 3번째, 6번째 인덱스 값과 관계되는 2차원 배열의 행 값을 보면 2차원 배열의 크기로 나누면 그 몫으로 맞아떨어지는 것으로 보인다.

위와 같이 유추를 통해 규칙성을 찾으면 될 것 같다.

다음에는

1. 머리로 풀려고 하지 말기

2. 노트에 적는걸 귀찮아 하지 말기

3. 시간에 쫓겨 조급해 하지 말기

---

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL