[Algorithm] 과제 진행하기

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/176962

💬 Idea

• Stack 구조를 사용한다.
• 진행하다가 멈춘 과제들을 Stack에 넣는다.
• Stack에서 마지막 원소를 꺼내어 현재 진행하고 있는 과제를 끝내는 시간보다 homework배열의 마지막 원소가 더 먼저 시작된다면
  • 남은 시간을 계산하고 업데이트하여 현재 진행하고 있는 과제를 stack에 다시 넣고
  • homework에서 새로 시작되어야할 과제도 stack에 넣어 마지막 원소가 되게끔 만든다.
  • 그리고 현재 시간 또한 새로 시작되어야할 과제 시간으로 업데이트한다.
• 작거나 같다면 정답 배열에 현재 수행이 완료된 과제의 이름을 넣는다.
  • 이 때 진행하던 과제는 더이상 없고 새로 해야하는 과제가 남아있다면, homework 배열의 마지막 원소를 꺼내 hwStack에 집어넣는다.

💬 풀이

import Foundation

struct Homework {
 var name: String
 var startHour: Int
 var startMinute: Int
 var playTime: Int
}

func solution(plans:[[String]]) -> [String] {
 var homework: [Homework] = []
 
 for i in plans {
 let time = i[1].components(separatedBy: ":").map({ Int($0)! })
 homework.append(Homework(name: i[0], startHour: time[0], startMinute: time[1], playTime: Int(i[2])!))
 }
 
 // 정렬
 homework = homework.sorted(by: { getTotalTime($0.startHour, $0.startMinute) > getTotalTime($1.startHour, $1.startMinute) })
 
 var hwStack: [Homework] = [homework.removeLast()]
 var currentHour: Int = hwStack[0].startHour
 var currentMinute: Int = hwStack[0].startMinute
 var ans: [String] = []
 
 while !hwStack.isEmpty {
 if var nowHW = hwStack.popLast() {
 nowHW.startHour = currentHour
 nowHW.startMinute = currentMinute
 
 if let nextHW = homework.last {
 // 과제 진행 중 새 과제를 해야한다면
 if getTotalTime(currentHour, currentMinute, nowHW.playTime) > getTotalTime(nextHW.startHour, nextHW.startMinute) {
 nowHW.playTime = nowHW.playTime - getIntervalTime(currentHour, currentMinute, nextHW.startHour, nextHW.startMinute)
 hwStack.append(nowHW)
 removeLastHomework(nextHW)
 } else {
 // 현재 과제가 마무리되었을 때
 ans.append(nowHW.name)
 let doneTime = getDoneHomeworkTime(currentHour, currentMinute, nowHW.playTime)
 currentHour = doneTime[0]
 currentMinute = doneTime[1]
 
 // 만약 하던 과제가 없지만 새로 해야하는 과제가 남아있다면
 if hwStack.isEmpty && !homework.isEmpty {
 removeLastHomework(nextHW)
 }
 }
 } else {
 ans.append(nowHW.name)
 }
 }
 }
 
 func removeLastHomework(_ nextHW: Homework) {
 hwStack.append(homework.removeLast())
 currentHour = nextHW.startHour
 currentMinute = nextHW.startMinute
 }
 
 return ans
}

// 총 시간을 구하는 메서드
func getTotalTime(_ startH: Int, _ startM: Int, _ playTime: Int? = nil) -> Int {
 if let playTime = playTime {
 if playTime + startM > 60 {
 return (startH + ((playTime + startM) / 60)) * 60 + ((playTime + startM) % 60)
 } else {
 return (startH * 60) + playTime + startM
 }
 }
 return startH * 60 + startM
}

// 시간 차를 구하는 메서드
func getIntervalTime(_ startH: Int, _ startM: Int, _ endH: Int, _ endM: Int) -> Int {
 if startH < endH {
 return (60 - startM) + (endH - (startH + 1)) + endM
 } else {
 return endM - startM
 }
}

func getDoneHomeworkTime(_ startH: Int, _ startM: Int, _ playTime: Int) -> [Int] {
 if startM + playTime > 60 {
 return [startH + ((playTime + startM) / 60), (playTime + startM) % 60]
 } else {
 return [startH, playTime + startM]
 }
}

소요시간 : 2시간

• 아이디어는 빨리 떠올렸으나, 구현 단계가 조금 오래 걸렸다… 구현 어렵다 !!