[Swift 알고리즘] 백준 1931 회의실 배정

△

그리디 Silver1

백준 1931번 회의실 배정

문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

1차시도 - 틀렸습니다.

엥?? 왜?? 

문제 보자마자 아 끝나는 시간을 기준으로 정렬해서 답을 구하면 되겠군! 이라고 생각해서 바로 풀었는데 

도대체 왜 틀렸다고 나오는거지???

끝나는 시간이 중요하니까 어짜피 시작 시간은 상관없는거 아닌가? 라고 생각했던 나의 오산,, 😨

회의의 시작시간과 끝나는 시간이 같을 수도 있다.

요 조건 때문에 생기는 예외 케이스가 있더라.

예를 들어 3 5, 3 3, 1 3 이렇게 시간이 주어지면, (1, 3), (3, 3), (3, 5) 로 해서 최대 개수는 3이 되어야 하지만, 

시작 시간 빼고 끝나는 시간으로만 정렬을 할 경우, (3, 3), (1, 3), (3, 5) 로 되어 최대 개수는 2가 나온다,,, 

따라서 끝나는 시간 뿐 아니라 시작 시간도 정렬을 같이 해줘야 한다는 ●(점)...! 

let n = Int(readLine()!)!
var meetings = [[Int]]()
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    meetings.append(input)
}

meetings = meetings.sorted(by: { $0[1] < $1[1] } )
var end = meetings[0][1]
var result = 1
for i in 1..<meetings.count {
    if end <= meetings[i][0] {
        result += 1
        end = meetings[i][1]
    }
}
print(result)

 

2차 시도 - 맞았습니다! 72236KB 164ms

let n = Int(readLine()!)!
var meetings = [(Int,Int)]()
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    meetings.append((input[0],input[1]))
}

meetings.sort{ ($0.0, $0.1) < ($1.0, $1.1) }

var end = 0
var count = 0
for meeting in meetings {
    if end <= meeting.0 {
        end = meeting.1
        count += 1
    }
}

 

+ 정렬해주는 방법

//풀어쓰면 이런 방식
meetings.sort {
    if $0.1 == $1.1 {
        return $0.0 < $1.0
    }
    return $0.1 < $1.1
}

//ternary 쓰면 요러케 됨
meetings.sort { $0.1 == $1.1 ? $0.0 < $1.0 : $0.1 < $1.1 }

//요러케 그냥 바로 알아서 비교하라고 할 수도 있움
meetings.sort { ($0.0, $0.1) < ($1.0, $1.1) }