[kotlin] 프로그래머스 - n^2 배열 자르기

문제를 풀었던 흔적을 보면서 배운 점들을 정리해보려고 한다...

 

문제 설명

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

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

n=1, left=2, right=5 예시

 

입출력 예

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

 

 

최종 정답

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray = (left..right)
        .map { maxOf(it%n, it/n).toInt() + 1 }
        .toIntArray()
}

---

첫 번째 시도

첫 번째 내 생각은 이랬다.

1. 문제: n*n 배열을 만들고... > 넵!!
2. 문제: 그 배열을 1차원으로 만들고... > 넵!!
3. 문제: 1차원 배열을 left부터 right까지를 리턴하라 > 넵넵!!

ㄹㅇ 문제를 곧이곧대로 받아들인 나...ㅎㅎㅎㅎㅎ

그렇게 나온 결과는 아래와 같다.

import kotlin.math.*

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
    	// 1
        val arrayNN = Array(n, { i -> Array(n, { j -> max(i, j) + 1 } ) })
        // 2
        var arrayFlat = intArrayOf()
        arrayNN.forEach { i ->
            i.forEach {
                arrayFlat += it
            }
        }
        // 3
        return arrayFlat.slice(left.toInt()..right.toInt()).toIntArray()
    }
}

 

몇몇 가벼운 문제들은 정답이긴 했다.

하지만 left, right가 Long이라는 점을 간과했다.

범위가 커지면 n^2 배열 크기와 그걸 flat화한 배열이 당연히 커질 텐데...

그래서 이 문제를 제출했을 땐 메모리 초과, 시간 초과 오류가 났었다.

 

두 번째 시도

아 그럼 left에서 right까지의 1차원 배열만 만들고 바로 제출하면 되네 ㅋㅋ < 라는 생각으로 아래와 같은 코드를 짬ㅋㅋ

import kotlin.math.max

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        var answer: IntArray = intArrayOf()
        
        (left.toInt()..right.toInt()).forEach {
            answer += max(it/n, it%n) + 1 
        }
        
        return answer
    }
}

 

아니 방금까지 left, right가 Long임을 간과했다고 했는데

그렇다고 바로 toInt로 형변환하는 건 머죠?

왜 이런 짧은 생각을 한 건지...

코테 하기 싫엇나보다.....

암튼 당연히 가벼운 문제는 정답이었지만

크기가 큰 문제들은 오류가 남... 메모리, 시간 초과는 아니고 그냥 "실패"

여기서 아 내가 멍청햇구나. Long을 살려야겠구나<를 깨달음

 

세 번째 시도

Long을 살리고 나누기 한 후의 값을 Int로 변환했더니 드뎌 나온 정답ㅠㅋㅋ

길었다...^^

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        var answer: IntArray = intArrayOf()
        (left..right).forEach {
            answer += maxOf(it%n, it/n).toInt() + 1
        }
        return answer
    }
}

 

 

최종 정답

드뎌 다른 사람들의 풀이를 볼 수 있어서 보다가 map으로 깔끔하게 코드짠 사람 보고 나도 해봄

아름답군요

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray = (left..right)
        .map { maxOf(it%n, it/n).toInt() + 1 }
        .toIntArray()
}

---

회고

담부터는... 숫자 범위를 잘 파악하고 범위에 맞는 풀이법을 먼저 고민해야겠다.

그동안 문제의 '제한 사항'을 잘 안읽었는데 이것만 잘 읽어도 이 문제는 금방 해결할 수 있을 듯!!

글고 문제가 이대로 푸시오.해도 ㄹㅇ 그대로 풀면 안되겠다는 생각을............<ㅋㅋㅋㅋ ㅠㅠ

문제가 그렇게 풀라고 해도 더 빠른 방법을 고민해보는 시간을 먼저 가져야겠다.

 

이 문제같은 경우는

범위, 더 빠른 방법 고민하는 것도 포인트 같지만,

이차원 배열을 다루는 법도 포인트 같았는데 이건 내가 잘 하는 거라 갠찬 

푸하하

팟팅팟팅