[Swift/Python] 백준 BOJ - 2170 선 긋기

Github

GitHub - jeongju9216/Algorithm: Swift/Python 알고리즘

 

문제 링크

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

 

풀이

정렬, 그리디로 해결할 수 있습니다.

 

1. 시작하는 점을 오름차순으로, 시작하는 기준이 같다면 끝나는 점을 오름차순으로 정렬합니다.
2. left, right에 0번 점의 start, end를 저장합니다.
3. 1번 점부터 반복을 시작합니다.
4. 점의 end가 right 보다 크다면 right를 갱신합니다.
5. 점의 start가 left보다 크면 left를 갱신합니다.

 

이 문제의 로직은 쉽습니다.

다만 설정된 시간제한이 너무 빡빡해서 시간초과가 심각하게 발생합니다.

Swift는 FileIO를 이용해 입력을 받아야 하고, 파이썬도 s, e를 list가 아니라 tuple로 받아야 한다네요.

아래 코드를 참고하시면 될 듯 합니다.

 

Swift 코드

import Foundation

final class FileIO {
private let buffer: Data
private var index: Int = 0

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

@inline(__always) private func read() -> UInt8 {
    defer {
        index += 1
    }
    guard index < buffer.count else { return 0 }
    
    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 str = ""
        var now = read()

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

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

let fileIO = FileIO()
let n = fileIO.readInt()
var lines: [(s: Int, e: Int)] = []
for _ in 0..<n {
    let s = fileIO.readInt()
    let e = fileIO.readInt()
    lines.append((s, e))
}

lines.sort {
    if $0.s != $1.s {
        return $0.s < $1.s
    } else {
        return $0.e < $1.e
    }
}

var left = lines[0].s, right = lines[0].e
var result = 0
for i in 1..<n {
    let line = lines[i]
    if right >= lines[i].e {
        continue
    }
    
    if line.s <= right && right < line.e {
        right = line.e
    } else if right < line.e {
        result += right - left
        left = line.s
        right = line.e
    }
}
result += right - left

print(result)

Python 코드

import sys; readLine = sys.stdin.readline

n = int(readLine())
lines = []
for _ in range(n):
  x, y = map(int, readLine().split())
  lines.append((x, y))

lines.sort()

left = lines[0][0]
right = lines[0][1]
result = 0

for i in range(1, n):
  if right >= lines[i][1]:
    continue

  if lines[i][0] <= right < lines[i][1]:
    right = lines[i][1]
  elif right < lines[i][0]:
    result += right - left
    left = lines[i][0]
    right = lines[i][1]
    
result += right - left
print(result)

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.

 

Swift, 스위프트, 파이썬, Python, 알고리즘, 백준, BOJ