[Algorithm] 백준 - 1334번 철로 (Swift)

문제 소개

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

문제 풀이

가장 간단한 풀이방법은 철로를 계속 한 칸씩 옮겨가면서 확인해 보기. 하지만 이 방법은 철로를 옮길 때마다 새롭게 그곳에 포함되는 선을 찾아야 한다는 점이다. 그렇다면 이 문제는 포함되는 선을 최대한 가져가면서 갱신해 주는 방식으로 사용하면 된다!

 

1. 철로를 어떻게 옮겨야 효율적으로 옮길까?

주어진 것은 집의 x좌표와 오피스의 x좌표이다. 이것을 기준으로 철로를 옮겨가면 되겠다는 생각을 했다. 어자피 철로의 길이는 마지막에 주어진 d보다만 작으면 최대로 포함만 한다면 길이는 상관없다. 그렇다면 집의 좌표, 오피스의 좌표로 옮겨가면서 철로의 길이가 d 이내인 두 점으로 순서대로 옮겨보면 되겠다고 생각했다.

 

2. 어떠한 식으로 포함되는 사람을 최대한 가져갈 수 있을까?

매번 철로를 갱신할때마다 포함되는 사람을 다시 찾는다면 분명 시간초과가 날 것이다. 결국 포함되는 사람을 저장해 놓고, 철로를 옮길 때마다 시작점과 마지막점을 가지고 포함되는 사람을 더해주거나 빼주는 방식으로 진행하면 된다. 그렇다면 시작점을 포함하면 +1을 해주고 마지막점을 포함하면 +1을 해주어서 2가 된다면 그 사람은 포함된다고 볼 수 있다.

 

위의 논리에 따라 아래와 같이 포인트를 두개로 나눠서 두 개를 저장한 후 정렬해 주었다. 이렇게 되면 h, o의 대소관계도 구분이 필요 없어지게 된다. (결국 둘 다 포함해야 하므로...)

let n = Int(readLine()!)!
var points = [(i: Int, x: Int)]()

for i in 0..<n {
    let ho = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let (h, o) = (ho[0], ho[1])
    
    points.append((i, h))
    points.append((i, o))
}

points.sort { $0.x < $1.x }

 

그리고 포인트를 기준으로 배열을 돌리면서 end를 지정해 주고 start를 end에 맞춰서 최대한 크게 잡아준다. start와 end에 따라서 check 배열에서 더하거나 빼준뒤 2가 되는지 안되는지 판단한다.

var check = Array(repeating: 0, count: n)

for point in points {
    let end = point.x
    let person = point.i
    
    while end - points[idx].x > d {
        let person = points[idx].i
        if check[person] == 2 { count -= 1 }
        check[person] -= 1
        idx += 1
    }
    
    check[person] += 1
    if check[person] == 2 { count += 1 }
    maxCount = max(maxCount, count)
}

 

정답 코드

import Foundation

let n = Int(readLine()!)!
var points = [(i: Int, x: Int)]()

for i in 0..<n {
    let ho = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let (h, o) = (ho[0], ho[1])
    
    points.append((i, h))
    points.append((i, o))
}

let d = Int(readLine()!)!

points.sort { $0.x < $1.x }

var idx = 0
var check = Array(repeating: 0, count: n)
var maxCount = 0
var count = 0

for point in points {
    let end = point.x
    let person = point.i
    
    while end - points[idx].x > d {
        let person = points[idx].i
        if check[person] == 2 { count -= 1 }
        check[person] -= 1
        idx += 1
    }
    
    check[person] += 1
    if check[person] == 2 { count += 1 }
    maxCount = max(maxCount, count)
}

print(maxCount)

 

입출력 라이브러리를 사용하지 않았을 땐 504ms, 사용했을 땐 76ms 가 나왔다!