kotlin 프로그래머스 lv2 n^2 배열 자르기

0

해당 문제를 정리해보면

n과 left , right는 매개변수로 주어진다.

예를들어 n = 3이고  left 와 right가 각각 2와 5라면 위의 영상과 같이 배열이 만들어진다.

나는 맨처음 이문제를 보자마자  2차원 배열을 생성하고,

그 후 그 리스트를 주어진 left와right 를 이용해서 잘랐다.

그래서 코드는 아래와 같이 작성했다.

 

 

하지만 제출 후 메모리 초과에러가 발생했다.

그래서 다른 블로그를 찾아보기로했다.

https://ongveloper.tistory.com/501

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

이분이 생각하신 부분 중에서 

 

이부분이 나와 생각이 같았다.

하지만 그 다음은 내가 접해보지 못한 백트래킹이란 알고리즘을 이용해서 풀어야한다고한다.

왜 시간초과가 난지 알겠다 ;;  

결과적으로 이런 코드가 나왔다.

글쓴이는 2차원 그래프에서 1차원 인덱스를 이용하여 다시 2차원 인덱스로 변환과정이 

"백트래킹"이라는 알고리즘을 이용한다고 했다.

솔직히 백트래킹을 잘 모르지만

1차원 인덱스를 2차원 인덱스로 바꾸는 방법을

쉽게 알아냈다.

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

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

 

이렇게 적었다.

인덱스를 left로 설정하고 answer배열의 사이즈를 

 IntArray((right-left).toInt()+1)

이렇게 하면 

 var idx = left  => 인덱스를 왼쪽부터 시작해서 right까지 간다고할때,

for(i in answer.indices){
            val r = (idx/n.toLong()).toInt()
            val c = (idx%n.toLong()).toInt()
            answer[i] = r.coerceAtLeast(c) +1
            idx++
        }

for문안에서 answer의 인덱스만큼 루프를 돌면서 요소를 채운다.

r.coerceAtLeast(c)는 r과 c를 비교했을때, r이 무조건적으로 크게끔 설정

해놨다. 

내가 혼자 풀때는 계속 에러가 났지만 다른 사람들의 풀이를 보니깐 몰랐던것도 알게되고

복습도 하게되는것 같았다.

 

뭔가 알고리즘을 알고 문제유형을 익힌다면 다음에 비슷한 문제가 나왔을때  풀 수 있을것 같은 기분이 든다.

 

• 1.의도 및 이유:  2차원 배열생성 후 주어진 매개변수 left와 right를 이용해 배열을 자른 후 새로운 배열 리턴하기위함
• 2.코드 동작 로직:  2중 for문을 이용해 주어진 nxn 크기의 2차원 직사각형을 채워나가는것처럼 코드 작성함  배열의 요소값은 현재 행과 열중 큰 값을 선택 후 1을 더함  그 후 완성된result 배열을 이용해서 left인덱스에서 right 인덱스까지 자름
• 버그 또는 에러 및 해결: 2차원 배열 생성 후 배열을 자르는 로직을 실행하니 메모리초과 에러가 발생했다. 아무리 수정해도 어떻게 할지몰라 검색을 했다.  백트래킹 알고리즘 원리를 이용해 해결했다.