백준 17829 222-풀링(Swift) 재귀활용

백준 17829 - 222-풀링

17829번: 222-풀링

접근법

• 재귀를 사용하여 푸는 문제로, 변의 길이가 n(2의 거듭제곱)을 가지는 정사각형이며 값이 하나 남을때까지 지속적으로 배열을 줄여주기로 한다.

첫 코드

func pooling(n: Int, arr: [[Int]]) -> [[Int]] {
    var temp: [Int] = []
    var tempList: [Int] = []
    var answer: [[Int]] = []

    if arr.count == 1 {
        return arr
    } else {
        for x in stride(from: 0, to: n, by: 2) {
            for y in stride(from: 0, to: n, by: 2) {
                for x1 in x..<x+2 {
                    for y1 in y..<y+2 {
                        temp.append(arr[x1][y1])
                    }
                }
                tempList.append(temp.sorted()[2])
                temp = []
            }
            answer.append(tempList)
            tempList = []
        }
        return pooling(n: n / 2, arr: answer)
    }
}

• arr배열의 카운트가 1일때 즉 배열이 계속 줄어들어 값이 하나뿐이 없을 때는 더 이상 줄일것이 없기 때문에 현재 arr을 리턴한다.
• 그 외에 동작으로는 n이 4일 경우 (0, 0), (0, 1), (1, 0), (1, 1)부터 (2, 2), (2, 3), (3, 2), (3, 3)까지의 배열을 잘라서 배열 중 2번째로 큰 값을 가져와야 한다.
• 첫 for문은 n이 4라면 0, 2를 가져오는 for문이고, 8이라면 0, 2, 4, 6으로 x값이 돈다.
• 두번째 for문 역시 마찬가지이며 이후 x1, y1 for문은 2 x 2의 배열을 잘라서 값에 넣는다.
• x1, y1의 for문이 끝날 경우 temp의 값을 정렬하여 뒤에서 2번째 값을 가져오며 for의 y문이 끝나면 해당 (0,0), (0, 2) ~~ (n, 0), (n, 2)까지의 각각 두번째로 큰 배열값을 가진 tempList가 answer로 이차원 배열형태로 저장된다.
• 이후 다시 pooling함수를 호출하고 2x2형태를 하나로 만들었기 때문에 n / 2와 현재 만들어진 이차원배열 answer을 인자로 넘겨준다.

정리한 코드

func cutArray(x: Int, y: Int, arr: [[Int]]) -> [Int] {
    var temp: [Int] = []
    for tempX in x..<x+2 {
        for tempY in y..<y+2 {
            temp.append(arr[tempX][tempY])
        }
    }

    return temp
}

func pooling(n: Int, arr: [[Int]]) -> [[Int]] {
    var temp: [Int] = []
    var tempList: [Int] = []
    var answer: [[Int]] = []

    if arr.count == 1 {
        return arr
    } else {
        for x in stride(from: 0, to: n, by: 2) {
            for y in stride(from: 0, to: n, by: 2) {
                temp = cutArray(x: x, y: y, arr: arr)
                tempList.append(temp.sorted()[2])
                temp = []
            }
            answer.append(tempList)
            tempList = []
        }
        return pooling(n: n / 2, arr: answer)
    }
}

let n = Int(readLine()!)!
var arr: [[Int]] = []

for _ in 0..<n {
    let x = readLine()!.split(separator: " ").map{ Int($0)! }
    arr.append(x)
}

print(pooling(n: n, arr: arr)[0][0])

• 2 x 2배열을 만드는 함수를 리턴해주는 함수를 만들어 기존 4중 for문 지옥에서 그나마 해방되어 보기에는 편안한? 코드로 만들었다.

• 생각보다 어려운 문제는 아니었으며, 간단히 재귀를 사용할 줄 알고 배열을 잘라내는 방법만 어느정도 생각하면 풀기 쉬운 문제였다.