프로그래머스 n^2 배열 자르기 Kotlin (구현)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/87390

코딩테스트 연습 - 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차원 배열을 만드는 과정을 나타낸 것입니다.

풀이

규칙만 찾으면 굉장히 짧은 코드로 풀 수 있는 문제.

우선 n의 크기에 압도된다.

당연한 얘기지만 요 정도 사이즈의 n을 주는 문제는 보통 O(NlogN) 이하로 풀어야 한다.

규칙을 찾으면 O(N)으로 가능할 것 같은 느낌~

 

일단 n이 n^7이기 때문에 직접 2차원 그래프를 만들 수는 없다.

이게 제약이라고 생각할 수도 있지만 사실은 힌트다.

2차원 그래프를 만들지 못한다는 것은 결국엔 어떠한 규칙이 있으니 그것을 찾아서 풀어라! 라는 뜻이다.

 

규칙을 찾기 위해 그래프를 그려보자

 

0,0	0,1	0,2	0,3
1,0	1,1	1,2	1,3
2,0	2,1	2,2	2,3
3,0	3,1	3,2	3,3

 

1	2	3	4
2	2	3	4
3	3	3	4
4	4	4	4

 

첫 번째 그래프는 2차원 그래프의 인덱스를 나타낸 것이고,

두 번째 그래프는 문제의 조건대로 값을 넣은 것이다.

이를 펼치면

1, 2, 3, 4, 2, 2, 3, 4, 3, 3, 3, 4, 4, 4, 4, 4

여기서 left~right를 출력하면 된다.

 

우선 규칙은 이미 보이겠지만 해당 칸의 r,c 인덱스 중 큰 값에 +1을 한 값을 넣어주면 된다.

0,0칸은 0+1

0,1칸은 1+1

3,2칸은 3+1

 

여기서 또 2차원 그래프를 1차원으로 펼칠 때, 행 순서대로 옆으로 이어 붙인다.

백트래킹 문제를 풀다 보면 간혹 2차원 그래프를 1차원 인덱스를 가지고 다시 2차원 인덱스로 변환하며 탐색해야 할 때가 있는데

이것을 해보았다면 쉽다.

 

1차원 인덱스를 2차원 인덱스(r,c)로 바꾸는 방법은 다음과 같다.

1차원 인덱스 / 가로 길이 = r(행)

1차원 인덱스 % 가로 길이 = c(열)

 

left~right만큼 반복하는 인덱스를 idx라 하자. 현재 그래프의 n은 4이다.

예제 2번을 보면 idx는 7부터 시작한다.

idx가 7일 때, 

r = 7/4 => 1

c = 7%4 =>3

 

1과 3 중에 큰 값 +1 => 4

 

하나만 더 해보자

 

idx가 8일 때,

r = 8/4 => 2

c = 8%4 =>0

 

2와 0 중에 큰 값 +1 => 3

 

답이 나왔다.

이렇게 left~right까지만 반복하면 끝

쉽쥬?

 

코드

class Solution {
    
    
    fun solution(n: Int, left: Long, right: Long): IntArray {
         
        var answer = IntArray((right-left).toInt()+1)
        
        var idx = left
        
        for(i in answer.indices){
            val r = (idx/n.toLong()).toInt()
            val c = (idx%n.toLong()).toInt()
            answer[i] = r.coerceAtLeast(c) +1
            idx++
        }
        
        return answer
    }
}