<프로그래머스> 쿼드압축 후 개수 세기(Lv.2)
[깃허브]
[프로그래머스]
https://school.programmers.co.kr/learn/courses/30/lessons/68936
이 문제는 분명 내가 해결했다고 생각했는데 제출하고 나서 엄청난 실패가 나와서 당황했다.
그리고나서는 다른 방법이 생각나지 않아 다른 사람들의 풀이를 참고하여 결과를 얻었다.
처음에 푼 방식은 반복문을 활용한 방식이었다.
기준이 되는 한 칸을 기준으로 주변 기준칸과 비교하는 식이었다.
말로 하니까 좀 이해하기가 힘들 수도 있는데 1칸짜리 사각형일 때는 제외하고 4칸짜리 사각형에서는 오른쪽 아래 칸을 기준칸으로 삼아 값을 비교하고 16칸짜리 사각형에서도 오른쪽 아래 칸을 기준칸으로 삼는데 다른 점은 이전 라운드의 기준칸들과 비교한다는 것이다.
4칸짜리 사각형들의 기준점 4개가 포함된 사각형이 16칸짜리 사각형인 거에서 생각해내고 진행한 거였다.
이부분들을 그대로 쓰다보니 코드는 좀 많이 길어지고 반복되고... 더러운 거 같기도?
어쨌든 이 방법은 대부분의 케이스를 실패했다.
이후에 질문을 통해 이유를 좀 알아보려고 한다.
(여기서 추가로 알게 된 것은 pow와 log2 함수는 kotlin.math를 임포트해야지 사용할 수 있다는 거였다.)
그 후 시간을 들이다가 다른 사람들의 풀이를 참고했는데 쿼드 트리 자체를 그대로 구현하는 분도 있었고 내가 하려던 방식처럼 보이는 걸로 해결하신 분도 있었다.
내가 선택한 방식은 재귀함수였다.
나도 문제를 처음 보자마자 떠오른 방식이 재귀였지만 구현에서는 안개가 낀 거처럼 막막해서 반복문으로 돌아간 거였다.
그래도 좀 힌트를 얻고 진행을 하니 어떻게든 뚫기는 뚫었다.
먼저 크기가 1인지 확인을 하고 크기가 1이 아니라면 해당 구역을 순회하며 모두 다 같은 값인지 확인한다.
같은 값이었다면 그냥 거기서 값을 올리면서 재귀를 끝내고 다른 값이라면 칸을 4부분으로 쪼개서 재귀함수를 실행한다.
이 알고리즘이 말로는 참 쉬운데 코드로는 왜그렇게 잘 안되는지 모르겠다.
해당 방법으로 작성한 코드는 다음과 같다.
class Solution {
var answer: IntArray = IntArray(2) {0}
fun solution(arr: Array<IntArray>): IntArray {
dfs(arr, 0, 0, arr.size)
return answer
}
private fun dfs(arr: Array<IntArray>, row: Int, col: Int, size: Int) {
// 크기가 1일 때
if (size == 1) {
if (arr[row][col] == 1) answer[1]++
else answer[0]++
return
}
// 크기가 1이 아닐 때
val start = arr[row][col]
var count = 0
// 해당 구역 순회
for (i in row until row + size) {
for (j in col until col + size) {
if (start == arr[i][j]) count++
}
}
// 모두 다 같은 값인 경우
if (count == size * size) {
if (start == 1) answer[1]++
else answer[0]++
return
}
// 다른 값이 있는 경우
dfs(arr, row, col, size / 2)
dfs(arr, row, col + size / 2, size / 2)
dfs(arr, row + size / 2, col, size / 2)
dfs(arr, row + size / 2, col + size / 2, size / 2)
}
}
요즘은 재귀가 해결방법으로 떠오르는 것까지는 도달한 거 같지만 해결방법으로써 작성하는 것은 아직 미숙한 것 같다.
지금 부족하게 느껴지는 재귀 문제는 따로 찾아서 풀어봐야겠다는 생각이 든다.