메모리초과와 시간초과의 싸움(feat. 승급!)

난 이때까지 removeFirst()가 O(1) 인 줄 알았다.
하지만 잘 생각해보면 맨 앞에를 지우고 배열을 정렬하기 위해 N-1 의 수행이 들어가기 때문에 O(N)이 걸린다.

2일간 쉽지 않은 문제를 풀었다. 사실 문제 자체가 어려운 것은 아니었다. BFS의 개념으로 그 전 문제를 풀다보니 이 문제도 어떻게 풀어야할지 로직은 금방 구현할 수 있었고, Testcase 또한 풀었다.

메모리 초과

25%에서 도저히 넘어가질 않았다. 이를 해결하기위해서 많은 삽질을 한 결과 해결하였다.
로직 상 현재 배열 element를 없애고 해당 원소가 조건에 맞으면 새로운 원소들을 추가하는 방식(BFS)인데 현재 배열을 저장할 새로운 2차원배열을 만들고 현재 배열을 삭제하는 식으로 구현했다.

//var fires = [[Int]]()
var curFire = fires //현재용도
fires = []//.removeAll()
            
curFire.forEach { fire in
	//fire가 조건에 맞으면//
        fires.append([nR,nC])
}

이런 방식을 하니 2차원배열을 계속 복사하다보니 메모리 초과가 났었다. 그래서 fire 자체만으로 구현했다.

var fires = [[Int]]()
for _ in 0..<fires.count {
    let fire = fires.removeFirst()
    //fire가 조건에 맞으면//
    fire.append([nR,nC])
}

시간 초과

하지만 이제는 시간초과가 났는데.. 여기서도 삽질을 했다. 이전에 작성한 파일입출력을 이용했는데도 불구하고 문제가 되었다. 그리고 이 문제를 푼 현무님의 블로그의 키워드를 보자마자 해결했다.
removeFirst()
이 함수가 BFS특성상 큰 입력이 주어진 testcase에서는 문제가 되었다. removeFirst()가 while()문 안에서 이뤄지기 때문에 크기가 클수록 컸다. 이 함수를 대체하기 위해서 시작,끝,차이 변수를 두어서 removeFirst()를 대체하였다.

var fires = [[Int]]()
var fs = 0
var fe = fires.count
var diff = 0

for i in fs..<fe {
    let fire = fires[i]
    //fire가 조건에 맞으면//
    fire.append([nR,nC])
    diff += 1   
}

fs = fe
fe += diff

이렇게 O(N)의 함수를 제거하니 시간초과를 벗어나서 풀게 되었다.

결론

BFS를 공부하려고 했지만 그 것 외에 메모리, 시간초과에 공부를 더 한 2일이 되었다.

그리고 대망의 골드승급!! 100문제 가까이 풀다보니 골드문제가 엄청 무섭지는 않게 되는 것 같다. 충분히 고민하고 모르면 배우는 자세로 답안을 확인하면 되니까! 예뻐서 좋았다.