[Swift] 백준 1780 - 종이의 개수

문제 바로가기

풀이

행렬의 원소들의 값이 모두 같지 않다면, 그 행렬을 9개로 나누고
나눠진 행렬의 원소들의 값들이 모두 같은지 계속해서 확인해야한다.

구현은 어렵지 않은데 시간초과가 문제였다.

나는 행렬의 가로, 세로가 3인 경우(원소가 9개 있을 때)엔 행렬을 9개로 나누지 않고 바로 그 값들을 확인하여 결과 배열에 넣어줌으로써 시간초과를 해결하였다.

제출한 코드

import Foundation

let N = Int(readLine()!)!
var matrix = [[Int]]()
var counts = [0,0,0]

for _ in 0..<N {
    let numArr = readLine()!.split(separator: " ").map{Int(String($0))!}
    matrix.append(numArr)
}

// 행렬의 원소들이 모두 같은지 확인
func isAllSame(_ matrix: [[Int]]) -> Bool {
    let first = matrix[0][0]
    
    if matrix.allSatisfy({
        $0.allSatisfy { $0 == first}
    }) { return true }
    
    return false
}

// 해당 행렬의 가로가 3일 때
func addToCounts(_ matrix: [[Int]], counts: inout [Int]) {
    for i in matrix {
        for j in i {
            counts[j+1] += 1
        }
    }
}

func checkMatrix(_ currentMatrix: [[Int]], counts: inout [Int]) {
    let first = currentMatrix[0][0]
    
    if isAllSame(currentMatrix) {
        counts[first + 1] += 1
        return
    }
    
    if currentMatrix[0].count == 3 {
        addToCounts(currentMatrix, counts: &counts)
        return
    }
    
    let width = currentMatrix[0].count / 3
    for i in 0...2 {
        for j in 0...2 {
            let x = i * width
            let y = j * width
            
             var tempMatrix = [[Int]]()
             Array(currentMatrix[x..<x+width]).forEach{
                 tempMatrix.append(Array($0[y..<y+width]))
             }
            checkMatrix(tempMatrix, counts: &counts)
        }
    }
}

checkMatrix(matrix, counts: &counts)
counts.forEach{
	print($0
}

• 결과 배열 count를 값이 변하는 매개변수로 쓰기 위해서 inout 키워드를 사용했다.

통과는 했지만,, 뭔가 더 좋은 풀이가 있을 것 같다.. 아쉽 억지로 풀어낸 듯한 기분..