[Swift] 백준 1780 종이의 개수

오늘 하루종일 풀려고 도전했는데 실패해서 결국 구글링을 했다..

이 문제에서 주어진 N의 최대값은 3^7 = 2187이다.

즉 N^2 = 4782969

1초에 2000만회 연산된다고 해서 

2초 = 4천만회안에 풀면되니까 O(N^2)로 풀면 될 줄 알았는데 .. 계속 시간초과 오류가 발생했다.

 

구글링 중 파이썬으로 푼 코드들을 Swift언어로 바꿔 풀어봐도.. 파이썬에서는 풀리지만 Swift에서는 풀리지 않았다ㅠㅠ

 

 O(N^2logN), O(NlogN) 등등 다양한 시간복잡도로 구현해봤는데 모두 실패했었다.

import Foundation

let N = Int(readLine()!)!

var matrix = [[Int]]()

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

var counts = [0, 0, 0]

func countPaper(_ paper: [[Int]], _ x: Int, _ y: Int, _ size: Int) {
    
    // 해당 부분이 모두 같은 수인지 확인
    var allSame = true
    let first = paper[x][y]
    for i in x..<x+size {
        for j in y..<y+size {
            // 다른 수가 있을 경우 반복문 탈출
            if paper[i][j] != first {
                allSame = false
                break
            }
        }
    }

    if allSame {
        // 해당 부분이 모두 같은 수일 경우, 해당 수에 해당하는 counts를 증가
        counts[first + 1] += 1
    } else {
        // 해당 부분이 모두 같은 수가 아닐 경우, 9개의 작은 종이로 분할하여 재귀호출
        let newSize = size / 3
        for i in 0..<3 {
            for j in 0..<3 {
                countPaper(paper, x + i * newSize, y + j * newSize, newSize)
            }
        }
    }
}

countPaper(matrix, 0, 0, N)

print(counts[0])
print(counts[1])
print(counts[2])

결국 완벽한 방법은 아니지만 반복문을 도는 도중 탈출하게하는 방법으로 시간초과를 면할 수 있었다.

아무래도 N^2에서 반복이 가장 많이 될 것 같아서 필요없는 반복을 하지 않도록 break를 추가해줬다.