프로그래머스_JS- n^2배열 자르기

nd098pkc·2022년 6월 19일
0

코딩테스트 준비

목록 보기
7/15
post-thumbnail

프로그래머스 월간챌린지 시즌3 레벨2 문제이다.

문제

글로만 보면 이해가 어려울것이라 생각했는지 상세한 설명도 첨부되어있다.
위 배열은 n이 3일 경우 만들어지는 배열이다위 배열을 행으로 잘라내어 이어붙이면 위와같이 되며 2번부터 5번인덱스까지 잘라내면 [3,2,2,3]이 된다.
핵심은 어떻게 효율적으로 잘라낸 부분만 출력할 수 있는지가 될것이다.

풀이과정

<입력>

  1. 배열의 크기 "n"(Number)
  2. 잘라낼 첫번째 인덱스 "left"(Number)
  3. 잘라낼 두번째 인덱스 "right"(Number)

<배열을 만들어서 잘라보기>

주어진 문제해결 과정 그대로 진행하면 비효율적일것 같다는 직감적인 느낌이 들지만 우선 직관적으로 문제해결과정 그대로 따라가보자
먼저 배열만들기 부터

let arr = Array.from({length: n},()=>new Array(n).fill(0)) // n*n 크기 2차배열을 0으로 초기화
for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
        arr[i][j]=Math.max(i+1,j+1)                        // i행, j열 중 큰숫자로 채워넣기
    }
}

위와 같은 과정을 끝내고 나면 보기와 같이 i번째 테두리를 i로 채운 2차배열이 완성된다.
그 다음은 이 2차원배열을 한줄로 이어붙여서 left부터 right까지 잘라내 출력하면 될것이다.

return arr.flatMap(v=>v).slice(left,right+1) //한줄로 이어붙여서 left부터 right까지 끊어주기

이 무식해보이는 코드는 결과가 어떻게될까?

if문을 통해 n의 범위별로 null을 리턴하는 방식으로 n의 크기를 예측해보았는데 6~8번 테스트케이스의 n이 약 900~1000이 되는걸로 확인되었다.
에러가 나는 테스트케이스 중에는 10번이 약 9000~10000 사이로 최소값을 가지는것으로 보인다.
따라서 위 방법으로는 n이 1000 까지는 가능하지만 n 값 1000~9000 사이에서 core dumped 에러를 유발하게 되는것으로 보인다.

n의 범위가 10,000,000까지라는것을 생각할때 아쉽지도 않은 결과이다.
그렇다면 우린 더 효율적인 방법을 찾야아한다.

<해보지 않아도 아는것>

한줄로 만들었을때의 index만으로 해당칸에 들어갈 숫자를 알 수 있으면 모든 배열을 만들어볼 필요 없이 답을 만들어낼 수 있을것이다. 그리고 규칙이 보인다면 쉽게 그 답을 찾을 수 있다.

사실 아까전에 배열을 만들 때 이미 해답은 나왔었는데 이 문제에 필요한 배열을 만들기 위해서는 해당 칸의 행과 열 번호 중 큰수가 들어간다는 것이다.
arr[i][j]=Math.max(i+1,j+1) 가 성립한다는데 힌트가 있다.
배열을 한줄로 만들었을 때의 idx와 2차원 배열에서의 i,j가 어떤 관계가 되는지 표현하는 것이 핵심이 되겠다.

   2차원            1차원
0,0 0,1 0,2       0, 1, 2
1,0 1,1 1,2  =>   3, 4, 5
2,0 2,1 2,2       6, 7, 8

i의 값은 1차원 index의 값을 n으로 나눠 소수점을 버린값과 같고
j의 값은 1차원 index의 값을 n으로 나눈 나머지와 같다는 것을 알 수 있다.
이를 수식으로 표현하면
i=Math.floor(index/n)
j=index%n
이 될것이다.
이를 배열 만들때 썼던 규칙에 적용시키면

arr[i][j] = arr[index] = Math.max(Math.floor(index/n)+1,index%n+1)

이 될것이다.
1차원 배열에서의 index값만 알면 해당 칸에 들어갈 숫자를 알 수 있게 된것이다.

우리는 잘라낼 구간의 index를 알고 있으므로 정답 배열을 만들어준 후 index에 해당하는 숫자를 순서대로 넣어주면 된다.

let arr = []
for(let i=left;i<=right;i++){
    arr.push(Math.max(Math.floor(index/n)+1,index%n+1)
}
    return arr

결과는n의 크기와 상관없이 잘라낼 부분만 탐색하므로 훨씬 빨라진 모습이다.

규칙을 찾아내는 문제같아서 퀴즈풀듯이 재미있게 풀었다.
머리 아플때 이런문제 한번씩 풀면 좋을것같다.

전체코드

function solution(n, left, right) {
	let arr = []
	for(let i=left;i<=right;i++){
    	arr.push(Math.max(Math.floor(index/n)+1,index%n+1)
  	}
    return arr
}
profile
늦게배운 코딩이 무섭다

0개의 댓글