[스위프트][백준 6068][💛골드 5] 시간 관리하기 (그리디)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

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

🧞‍♂️ 풀이 방법

1. (필요한 시간, 끝나는 시간) 의 형태로 배열을 만든다
2. 끝나는 시간을 기준으로 역순으로 정렬시킨다
3. 마지막 끝나는 시간을 현재 시간으로 초기화해놓고, for 문 돌면서 필요한 시간을 하나씩 빼준다.
   • 이때 다음 끝나는 시간이랑 현재 시간을 비교해서, 끝나는 시간이 더 클 경우에는 더 일찍 시작 해야된다는 뜻이다.
   • 그래서 이때 끝나는 시간 - 현재 시간 의 최대값을 기록해둔다.
4. 마지막에 남는 시간에서 이 최대값을 빼준게 정답이다(0보다 작으면 -1을 출력한다)

굳이 반대로 안해도될것 같긴한데 그게 이해하기 편했습니다.

🧞‍♂️ 스위프트 코드

import Foundation

typealias Task=(duration: Int, dueTime: Int)

func solution(_ tasks: [Task]) -> Int {
    let tasks = tasks.sorted(by: {
        $0.dueTime > $1.dueTime
    })
    let taskCount = tasks.count
    var requiredTime = 0
    var startTime = tasks[0].dueTime // 시작 시간을 마지막 시간으로 초기화

    for i in 1..<taskCount {
        startTime -= tasks[i-1].duration
        if startTime > tasks[i].dueTime {
            requiredTime = max(requiredTime, startTime-tasks[i].dueTime)
        }
    }
    startTime -= tasks[taskCount-1].duration // 마지막 일 빼주기
    startTime -= requiredTime // 부족한 시간 만큼 빼주기

    return startTime >= 0 ? startTime : -1
}

let N = Int(readLine()!)!
var tasks: [Task] = []

for _ in 0..<N {
    let TS = readLine()!.split(separator: " ").compactMap { Int($0) }

    tasks.append(Task(TS[0], TS[1]))
}

print(solution(tasks))

🧞‍♂️ 생각해본 TC

6
1 1
1 2
1 3
1 4
1 5
1 6
-> 0
5
1 1
2 3
1 4
1 5
2 6
-> -1
4
3 5
8 15
5 20
2 16
-> 2
4
3 5
8 15
5 19
2 16
-> 1
4
3 5
8 15
5 17
2 16

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기