완전탐색 - 카펫

완전탐색 - 카펫(programmers.co.kr/learn/courses/30/lessons/42842?language=kotlin) 을 풀어봤습니다.

 

    fun Level_2_카펫(brown: Int, yellow: Int): IntArray {
        val sum = brown + yellow
        val half = sqrt(sum.toFloat()).toInt()
        val divisors = mutableListOf<Int>()
        for (i in 1..half) {
            if (sum % i == 0) {
                divisors.add(i)
                divisors.add(sum / i)
            }
        }

        return setResult(divisors.sorted().toSet(), yellow)
    }

    fun setResult(set: Set<Int>, yellow: Int): IntArray {
        val mid = set.size/2
        if (set.size % 2 == 0) {
            var index = mid
            for (i in mid until set.size) {
                index -= 1
                if ((set.elementAt(i)-2) * (set.elementAt(index)-2) == yellow) {
                    return intArrayOf(set.elementAt(i), set.elementAt(index))
                }
            }
        } else {
            return intArrayOf(set.elementAt(mid), set.elementAt(mid)).sortedArrayDescending()
        }
        return intArrayOf()
    }

위처럼 풀었다. 길다... 길어.... 여튼 푼 방식은

브라운의 개수의 가로-2 * 세로-2 가 옐로우의 개수라는 문제를 분석해 아래처럼 생각했다.

1. 전체 개수(brown+yellow)의 약수를 구한다.

2. 약수들의 set를 setResult에 넣은 다음, size가 홀수이면 그대로 중간 값을, 짝수이면 if문을 타게 한다.

3. if문 내에서는 set의 요소를 가져와 가로-2와 세로-2의 곱이 yellow와 같을 경우 해당 값을 return하게 만들었다.

 

짠!!! 엄청 효율적이진 않은거 같지만... 일단 만들었고 잘 동작했다. 중요한건 4, 6, 7번이다.

예제는 아래와 같이 테스트했다.

 

Level_2_카펫(10, 2)
Level_2_카펫(8, 1)
Level_2_카펫(24, 24)
Level_2_카펫(14, 4)
Level_2_카펫(18, 6)

 

다 통과하면 합격!

 

 

통과하고 나서 누군가의 풀이를 보고 현타가 왔다... 알고리즘 왜하지...

 

그분의 코드는 아래와 같다.

    fun setResult(brown: Int, yellow: Int): IntArray {
        return (1 .. yellow).filter {
            yellow%it == 0
        }.first {
            brown == (yellow/it*2) + (it * 2) + 4
        }.let {
            intArrayOf(yellow/it+2, it+2)
        }
    }

분석해 보자면,

filter를 통해 yellow의 약수들의 list를 구한다.

first를 통해 약수들을 차례대로 yellow를 나누고 * 2를 곱한 값(가로의 길이*2) 에 약수*2(세로의 길이*2) + 4(꼭지점의 개수) 를 더하면, brown과 같다.

예를 들어, 

 

ㅂㅂㅂㅂㅂㅂㅂㅂ

ㅂㅇㅇㅇㅇㅇㅇㅂ

ㅂㅂㅂㅂㅂㅂㅂㅂ

 

18, 6 을 예로 보자.(ㅂ : 브라운, ㅇ : 옐로우) 

filter를 통해 1..6 까지의 약수들의 집합을 구한다(1, 2, 3, 6)

first를 통해 (6 / (1, 2, 3, 6) * 2) + ((1, 2, 3, 6) * 2) + 4 = 18 이 됐을 때 

let을 통해 해당 가로, 세로를 intArraOf에 담아 내보낸다.

 

first를 보면, 6/1*2 는 아래 빨간색을 의미한다. 1*2의 경운 노란색을, +4는 초록색을 의미한다.

ㅂㅂㅂㅂㅂㅂㅂㅂ

ㅂㅇㅇㅇㅇㅇㅇㅂ

ㅂㅂㅂㅂㅂㅂㅂㅂ

 

만드신분 진짜 대단하다... 난 왜 이런 머리가 없을까 자책해본다....