💡 문제
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
- n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.- 1행 1열부터
i행i열까지의 영역 내의 모든 빈 칸을 숫자i로 채웁니다.
- 1행 1열부터
- 1행, 2행, ...,
n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. - 새로운 1차원 배열을
arr이라 할 때,arr[left],arr[left+1], ...,arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
⚠️ 제한사항
- 1 ≤
n≤ - 0 ≤
left≤right< right-left<
✅ 풀이
👆 첫 번째 풀이 (실패)
- n * n 크기의 2차원 리스트를 만든다.
- 각 칸의 행 번호와 열 번호 중 더 큰 값이 곧 해당 칸의 값이 된다.
- 2차원 리스트를 평탄화 시켜 자르는 방법도 있겠지만, 나는 left가 위치한 행부터 right가 위치한 행까지 먼저 크게 잘라주었다.
- 왜냐하면 left와 right가 Long형이여서 바로 slice 함수에 넣어줄 수 없었다.
- 그 후, 잘라진 리스트를 평탄화 해 left 부터 left + (right - left)의 길이만큼 다시 잘라주었다.
class Solution {
fun solution(n: Int, left: Long, right: Long): IntArray {
val list = List(n) { col -> List(n) { row -> if (col > row) col+1 else row+1 } }
val len = (right - left).toInt()
val (startCol, startRow) = Pair((left / n).toInt(), (left % n).toInt())
val (endCol, endRow) = Pair((right / n).toInt(), (right % n).toInt())
val t = list.slice(startCol..endCol).flatten().slice(startRow..startRow+len)
return t.toIntArray()
}
}제한사항을 무시한 나는 메모리 초과와 시간 초과라는 결과를 만나게 되었다.
- 메모리 초과: 리스트에 너무 많은 값을 저장했다. (n * n의 크기는 생각보다 컸다.)
- 시간 초과: 리스트를 초기화할 때 너무 많은 시간이 소요되고, 자르고 > 평탄화하고 > 다시 자르는 과정도 비효율적이다.
✌️ 두 번째 풀이 (성공)
- 각 칸의 값들은 "행과 열 중 더 큰 값"이다는게 중요하다.
- 구하려는 배열의 크기(right - left)는 생각보다 작다.
- 굳이 n * n의 배열을 다 초기화해 줄 필요가 없다.
- 애초에 left가 있는 행부터 right가 있는 행까지만의 배열을 만들었다.
- 이 때의 행 번호는 left / n 부터 시작한다.
- 즉, left / n 행부터 right / n 행까지의 배열을 만들면 된다.
- 배열을 잘라줄 때는 첫 번째 풀이에서 한 것처럼 시작 인덱스부터 시작 인덱스에 구하고자 하는 길이를 더한 인덱스까지 자르는 방식을 사용했다.
class Solution {
fun solution(n: Int, left: Long, right: Long): IntArray {
val len = (right - left).toInt()
val cols = (right/n - left/n).toInt()
val realStart = (left % n).toInt()
val list = List(cols+1) { col -> List(n) { row -> if (left/n+col > row) (left/n+col+1).toInt() else row+1 } }
return list.flatten().slice(realStart..realStart+len).toIntArray()
}
}최대값을 구할 때 조건문 말고 max()를 사용하는 방법이 있겠지만, 일단 그냥 풀어보았다. 문제 풀이에는 성공했지만 마음에 드는 풀이는 아니었다. 배열을 초기화하는데 사용되는 변수들이 너무 많고, 정수형 배열로 변환해주어야 하는 것도 마음에 안들었다.
🔥 다른 사람의 풀이
내가 너무 어렵게 생각했던 걸까? 다른 사람들의 풀이를 보니 생각보다 간단히 풀리는 문제였다. 내가 미처 생각하지 못했던 건, i번째 칸의 값을 배열의 초기화 없이 구할 수 있다는 것이다.
- i번째 칸의 행 번호는
i / n + 1이다.- 문제에서의 배열은 0이 아닌 1부터 시작하기 때문에 1을 더해줘야 한다.
- i번째 칸의 열 번호는
i % n + 1이다. - 이걸 이용해 left부터 right까지의 값을 구할 수 있다.
문제에서 2차원 배열을 만들고.. 1차원으로 만들고.. left부터 right까지 자르고.. 하는 과정으로 설명했다보니까 너무 거기에 갇혀있었던 것 같다.
import kotlin.math.max
class Solution {
fun solution(n: Int, left: Long, right: Long): IntArray {
return (left..right).map {
max(
it / n + 1,
it % n + 1
).toInt()
}.toIntArray()
}
}💭 후기
정말 간단한 문제였는데.. 너무 돌아돌아 푼 것 같다. 심지어 두 번째 풀이에서 left와 right를 이용해 행과 열의 번호도 구했으면서!! 왜 눈치채지 못했을까!! 너무 아쉽다. 그렇지만 이 문제 덕분에 2차원 배열을 초기화하는 걸 연습할 수 있어서 좋았다. 언젠가 쓰일 날이 오겠지.
화이팅