[프로그래머스] 힙(Heap) 42627 Swift

✅ 드! 디! 어! Level 3 문제를 해결했다 ~_~

 

물론,,, 그래프나 트리 등 다른 부분에서 부족한 점이 많지만, 우선 해결한 것에 정말 큰 기쁨을!

자료구조 힙은 하나의 트리라고 하는데, 막상 구현을 하나의 트리로 한 것 같지가 않고,

내 생각에도 시간복잡도의 개선점을 훨씬 더 가져갈 수 있는 부분인데, 그렇지 못한 것 같아서 매우 아쉬움!

 

🔶 문제를 풀면서 조금 어려웠던 부분 (코드에 다 있으니까 천천히 읽어보기)

1. 2차원 배열에서의 정렬 방법 

2. 문제를 파악하는 능력

 

특히 2번의 경우에는 생각보다 치명적이였는데, 스케줄러가 쉬는 시간도 포함하여 계산을 하였더니, 당연히 히든 케이스에서 틀림!!

(학교 수업시간에는 이것도 계산하는 걸로 공부한 것 같은데 음...)

아무튼!! 문제는 그렇지 않으니까, 꼼꼼하게 읽어보니 들어와서 종료한 시각 즉, 작업 시간만을 말하는 것을 알 수 있었다.

 

문제가 조금 더 테케가 늘고 직접적이였다면 좋았을 것만,, 아무튼 해결 끄읏

 

//
//  main.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/11/16.
//  https://programmers.co.kr/learn/courses/30/lessons/42627

import Foundation

func solution(_ jobs:[[Int]]) -> Int {
    
    let jobs = jobs.sorted(by: {$0[0] < $1[0] }) // 최소값으로 정렬
    print(jobs)
    var time = 0
    var RunningQueue = [[Int]]() // 언제나 하나만 존재해야 한다.
    var ReadyQueue = [[Int]]()
    var offset = 0 // 처음에 하나 넣고 시작하니까 배열 오프셋은 1
    var WaitingTime = 0
    var tm = 0
    //RunningQueue.append(jobs.first!) // 처음에 하나 넣자
    
    while true {
        
        // 종료조건
        if offset > jobs.count - 1 {
            if ReadyQueue.isEmpty && RunningQueue.isEmpty {
                break
            }
        }
        
        // Ready Queue 세팅
        for i in offset..<jobs.count {
            if jobs[i][0] <= time {
//                print("in")
                ReadyQueue.append(jobs[i])
                offset += 1
            } else {
                break
            }
        }
        
        // Running Queue 세팅
        if !ReadyQueue.isEmpty { // 비어있지 않다면
            ReadyQueue = ReadyQueue.sorted(by: {$0[1] < $1[1] }) // 최소값으로 정렬
            RunningQueue.append(ReadyQueue.first!)
            ReadyQueue.removeFirst()
//            print("w+ \(time - RunningQueue[0][0])")
            WaitingTime += time - RunningQueue[0][0] // waiting 시간 더해주기
        } else { // 비어 있다면
//            print("continue")
            time += 1
            tm += 1
            continue
            
//            RunningQueue.append(jobs[offset])
//            print("id+ \(RunningQueue[0][0] - time)")
//            WaitingTime += RunningQueue[0][0] - time // idle 시간 더해주기
//            offset += 1
        }
        
//        print("+ \(RunningQueue[0][1])")
        time += RunningQueue[0][1]
        
//        print("현재 시간은 \(time)")
        RunningQueue.removeFirst()
        
    }
//    WaitingTime = 0
//    print("time \(time) Wait \(WaitingTime) tm \(tm) / \(jobs.count)")
    return (time + WaitingTime - tm) / jobs.count
}

//var arr = [[0, 3], [1, 9], [2, 6]]
//print(solution([[0, 3], [1, 9], [2, 6]]))
//print(solution([[0, 9], [0, 4], [0, 5], [0, 7], [0, 3]]))
//print(solution([[0, 3], [4, 6]]))
//print(solution([[0, 3], [4, 4], [5, 3], [4, 1]]))
print(solution([[0, 3], [1, 9], [500, 6]]))



//let sortedArray = arr.sorted(by: {$0[1] < $1[1] })
//print(sortedArray)

//var a = 0
//var b = 0
//
//for i in a..<10 {
//    print("i is \(i)")
//    if i % 2 == 1 {
//        a += 1
//    }
//}
//
//print(a)

//let array = [ [0,2], [4,5], [4,1], [0,4] ]
//let result = array.max(by: {$0[1] < $1[1]}) //[0,2]
//print(result)

 

테스트 케이스 추가해줘야쥐~