메모리초과와 시간초과의 싸움(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문제 가까이 풀다보니 골드문제가 엄청 무섭지는 않게 되는 것 같다. 충분히 고민하고 모르면 배우는 자세로 답안을 확인하면 되니까! 예뻐서 좋았다.
Author And Source
이 문제에 관하여(메모리초과와 시간초과의 싸움(feat. 승급!)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rarebook92/메모리초과와-시간초과의-싸움저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)