[백준] (Swift) 2170번 - 선긋기 (시간초과 보류, 골드5, 그리디)

아주 쉽게 풀릴줄 알고 블로그 업로드를 하지 않으려고 했는데... 시간초과가 떴다.
근데, 이것저것 찾아보고 백준을 뒤져보니, 이 문제는 뭔가 swift로 풀 수 없는 문제 인것 같다는 판단이 내려졌다. (내 스스로)

⏰ 왜 시간초과 보류?

뭔가 이 문제는 시간초과 문제를 해결할 수 없을 것이라는 판단이 섰다. 왜냐면?

1. 일단, 나는 풀이과정에 잘못된 점을 찾지 못했다.

인터넷을 찾아보니 나와 동일한 방식으로 푼 C++, python등의 모든 코드들은 통과하는 것을 볼 수 있었다. 그렇다면 swift로 풀었을때 이 풀이과정이 안된다는 것은 말이 되지 않았다. 

2. 시간복잡도는 O(N)인데, 100만이 통과되지 않는 것이 이해할 수 없다.

지금까지 스위프트로 푼 문제들로 보았을 때, 1초가 주어졌다면 O(N), O(1)이면 통과할 수 있었다. 근데 왜 이 문제만 통과가 힘들다는 것일까? 우선 백준에서 문제를 풀 때 스위프트가 타 언어보다 조금 느리고 성능이 구리다는 사실은 알고 있다. 느리다고 소문난 파이썬과 당장 비교해보았을때, 파이썬으로 함수를 호출하는 시간보다 스위프트로 함수를 호출하는 시간이 훨씬 길다고 한다. (백준에서)

그래서, 나는 이번 문제를 Solution()이라는 함수를 만들어서 마지막에 함수를 호출하는 방식으로 풀었는데, 함수호출방식을 지우고 print로 바로뽑아버리는 방식을 사용해도 시간초과가 나는 것은 똑같다. 

일단,, 이 문제는 보류,,,,

---

⚫️ 문제

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

⚫️ 풀이 방법

풀이 방법은 아주 간단하게 생각해낼 수 있다. 주어진 input들을 x를 기준으로 오름차순 해준 뒤, end지점을 확인해보는 것이다. end까지 연결이 가능하면 end를 갱신해주고, 만약 예시와 같이 끊겨있다면 start와 end모두 새롭게 갱신하는 방식으로 진행했다.

그렇게 푼 첫번째 풀이,, - 시간초과가 떴다.

import Foundation

private func solution() -> Int {
    let n = Int(readLine()!)!
    var xy = [[Int]]()

    for _ in 0..<n {
        xy.append(readLine()!.split(separator: " ").map{ Int($0)! })
    }

    xy = xy.sorted{ $0[0] < $1[0] }

    var answer = 0
    var start = xy[0][0]
    var end = xy[0][1]

    for i in 1..<n {
        if end < xy[i][0] {
            answer += end - start
            start = xy[i][0]
            end = xy[i][1]
        } else {
            if xy[i][1] <= end {
                continue
            } else {
                end = xy[i][1]
            }
        }
    }

    answer += end - start
    return answer
}

print(solution())

물론, 시간을 아예 고려하지 않고 푼 것은 아니다. 단일 for문만을 사용할 예정이었고 N은 100만 이하로 들어오기 때문에, 아무리 for문을 최대로 돌려도 100만회 이하일 것이라고 판단했고, 이렇게 되면 1초는 충분히 가능하다고 판단했다. (O(N)) 근데 웨않되...