03/27 알고리즘 공부(79) - 카펫

조건

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한조건

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown	yellow	return
10	2	[4,3]
8	1	[3,3]
24	24	[8,6]

알고리즘 예상

1. 한 칸의 넓이를 1이라고 생각하면 전체 카펫의 넓이는 brown + yellow의 값이 된다.
2. 가로의 길이를 x, 세로의 길이를 y라고 하면 x * y = brown + yellow이므로 반복문을 통해 넓이의 약수쌍을 찾는다.
3. 넓이의 약수쌍 중 (2x + 2y - 4) == brown를 만족하는 약수 쌍을 찾는다. 단, 이 때 가로길이가 반드시 세로길이보다 길다고 했으므로 작은 값을 세로에 넣어야한다.
4. 해당 약수 쌍을 반환한다. 

초기 코드

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        var answer = intArrayOf()
        return answer
    }
}

 

내 코드

//통과
class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        var answer = intArrayOf(0, 0)
        val area = brown + yellow
        val measureList = mutableListOf<Pair<Int, Int>>()
        for (i in 1..Math.sqrt(area.toDouble()).toInt()){
            if (area % i == 0){
                measureList.add(i to area/i)
            }
        }
        measureList.first { 2 * (it.first + it.second - 2) == brown }.run { 
            answer[0] = second
            answer[1] = first
        }
        return answer
    }
}

정말 단순하게 풀었다. 탐색 범위를 좁히기 위해 sqrt를 이용했다. 조건문 중첩을 통해서도 풀 수 있기는 하지만 분리하는 편이 가독성이 좋아보여 분리했다. answer 변수가 필요없어 보여 지워보기로 했다.

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        val area = brown + yellow
        val measureList = mutableListOf<Pair<Int, Int>>()
        for (i in 1..Math.sqrt(area.toDouble()).toInt()) {
            if (area % i == 0) {
                measureList.add(i to area / i)
            }
        }
        return measureList
        .first { 2 * (it.first + it.second - 2) == brown }
        .run { intArrayOf(second, first) }
}

다른 사람의 풀이

//red -> yellow
class Solution {
    fun solution(brown: Int, red: Int): IntArray {
        return (1..red)
            .filter { red % it == 0 }
            .first { brown == (red / it * 2) + (it * 2) + 4 }
            .let { intArrayOf(red / it + 2, it + 2) }
    }
}

 

개선점 또는 배운점

1. 위 풀이는 전체 카펫의 넓이가 아닌 red의 넓이에서 검사를 진행했다.
   it은 red의 세로길이, red / it은 red의 가로길이이다.
   brown은 red의 가로길이, 세로길이를 2배씩 더하고 각 모서리 4만큼 더한 값이기 때문에 해당 조건을 만족하면 red의 가로길이와 세로길이를 알 수 있다.
   카펫의 가로길이와 세로길이는 red의 가로길이와 세로길이에 2씩 더한 값을 가지고 있으므로 해당 값을 리턴한다. 

개선된 코드

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        val area = brown + yellow
        return (1..Math.sqrt(area.toDouble()).toInt())
            .first { area % it == 0 && 2 * (area / it + it - 2) == brown }
            .let { intArrayOf(area / it, it) }
    }
}

filter를 사용하지 않고 first안에 조건을 두 개 넣었다.