백준 7578번 공장 - 스위프트(Swift) 시간초과 해결

 또 돌아온 시간 초과 해결 글ㅎㅎ CLASS 6 문제 훑어보다가 펜윅트리로 또 쉽게 풀리는 문제가 있어서 풀기 시작. 바로 전 문제에서 펜윅트리를 구현해둬서 거의 복붙 수준으로 풀 수 있었다. 근데.. 또 TLE를 맞았다.

 일단 풀이를 간단히 하자면, 먼저 기계 식별 번호를 인덱스 번호로 치환하자.

 

 이제 아래 라인을 기준으로 왼쪽부터 차례로 윗 라인과 대응시켜보자. 아래 4와 위의 4를 연결하는 선을 그었는데, 후에 3, 2, 1을 연결하는 선을 그을 때, 방금 그은 선과 교차할 것이다. 위쪽 라인에서는 4보다 왼쪽에 있고, 아래쪽 라인에서는 4보다 오른쪽에 있기 때문에 교차할 수밖에 없다. 즉, 아래쪽 라인을 기준으로 왼쪽부터 차례로 대응시켜나갈 건데, 위쪽 라인에서는 x보다 왼쪽에 있고, 아래쪽 라인에서는 x보다 오른쪽에 있는 것들을 카운트 해주면 된다. 이때 위쪽 라인은 오름차순으로 정렬되어 있으므로, 위쪽 라인에서 x보다 왼쪽에 있는 수들은 전부 x보다 작은 수들이다. 따라서 결국 이 문제는, 아래쪽 라인에서 각 기계에 대해 해당 기계보다 오른쪽에 있는 기계 중 더 작은 번호를 가진 기계의 개수들의 합이 된다.

 arr[i]를 i번 기계가 아직 대응되지 않았는지 여부(대응 안됐으면 1, 됐으면 0)로 두면, i번 기계와 교차하는 기계의 수는 arr[1...(i-1)]의 구간합과 같다. (왼쪽부터 차례로 대응시키고 있으므로, 아직 대응이 안됐으면 i번 기계보다 오른쪽에 있는 것이기 때문이다.) 위의 상황으로 치면 arr[1] + arr[2] + arr[3]을 구하면 된다. 모두 아직 대응시키지 않았으므로 1+1+1=3이다. 이제 4는 대응을 완료했으므로 arr[4] = 0으로 업데이트해준다. 이렇게 계속해서 변화하는 배열에서의 구간합을 구하는 문제이므로 펜윅트리를 써주었다.

 

 이제 다시 시간초과 이야기로 돌아오면,,, 위에서 인덱스 번호로 치환하는 과정에서 윗 라인을 가지고 딕셔너리를 만들었는데, 딕셔너리 만들고 읽는 코스트가 꽤 큰가 보다ㅠㅠ 그냥 배열로 바꿨더니 시간 안에 통과가 됐다. 얼마나 차이가 나는지 보려고 실험을 하나 해봤다. 10,000,000개의 데이터를 쓰고 읽는 데 걸리는 시간을 측정해봤는데, 1.7배 정도 차이가 났다.

// 딕셔너리
let dictStart = CFAbsoluteTimeGetCurrent()
var dict = [Int:Int]()
for i in 1...10000000 { dict[i] = i }
for i in 1...10000000 { _ = dict[i]! }
let dictEnd = CFAbsoluteTimeGetCurrent()
print(dictEnd - dictStart) // 13.090715050697327 

// 배열
let arrStart = CFAbsoluteTimeGetCurrent()
var arr = Array(repeating: -1, count: 10000001)
for i in 1...10000000 { arr[i] = i }
for i in 1...10000000 { _ = arr[i] }
let arrEnd = CFAbsoluteTimeGetCurrent()
print(arrEnd - arrStart)    // 7.8502219915390015

 

메모리가 넉넉하면 딕셔너리 쓰지말고 그냥 배열 쓰자:)