만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 2170 선 긋기

23 Jun 2021

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

선분의 시작과 끝이 주어지고 그러한 선들이 n개 있다고 할 때 그려지는 선들의 총 길이를 구하는 문제이다. 이 때 겹치는 부분은 1번만 계산한다. 스위핑에 대해 감을 익히기 좋은 문제인것 같다. 선들을 시작점을 기준으로 sort한다고 생각하자. 그렇다면 연속된 두 선분의 관계는 다음 세 경우로 나뉜다.

1. line[i].end <= line[i+1].start
2. line[i].end > line[i+1].start && line[i].end >= line[1+1].end
3. line[i].end > line[i+1].start && line[i].end < line[i+1].end
  1. 1번의 경우에는 두개의 선분이 겹치는 부분이 없을때이므로 새로운 선분의 길이를 더해주면 된다.
  2. 2, 3번의 경우에는 두개의 선분이 겹치는 부분이 생긴다. 이 때 뒷 선분이 앞 선분에 포함되는 경우가 2번에 해당한다. 새로운 선분의 길이는 이 때 전부 겹치기 때문에 더해줄 필요가 없이 넘어간다.
  3. 3번의 경우에는 뒷 선분의 end와 앞 선분의 end의 차만큼을 더해줘야 한다.
var left = -1_000_000_000, right = -1_000_000_000, result = 0
for l in line {
    if right < l.0 {
        left = l.0
        right = l.1
        result += right-left
    }
    //case 1
    else if l.1 > right {
        result += l.1-right
        right = l.1
    }
    //case 3
}

이 때 단순히 앞 선분과 비교를 하는 것이 아니라 여지껏 누적해온 선분들의 가장 오른쪽 좌표와 비교를 해야하기 때문에 right라는 변수를 활용하여 이를 비교해주었다.

파일의 입력이 크기때문에 fread를 해줘야 시간초과가 안난다. 관련 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였다. <출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>

/*
 fread를 위한 코드로는 JCSooHwanCho님의 FileIO.swift를 참조하였습니다.
 출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88
 */

import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

let fIO = FileIO()
let n = fIO.readInt()
var line:[(Int, Int)] = Array(repeating: (0,0), count: n)
for i in 0..<n {
    let x = fIO.readInt(), y = fIO.readInt()
    line[i] = (x, y)
}
line.sort(by: {$0.0 < $1.0})

var left = -1_000_000_000, right = -1_000_000_000, result = 0
for l in line {
    if right < l.0 {
        left = l.0
        right = l.1
        result += right-left
    }
    else if l.1 > right {
        result += l.1-right
        right = l.1
    }
}
print(result)

Related posts