점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
n | lost | reserve | return |
---|---|---|---|
5 | [2,4] | [1,3,5] | 5 |
5 | [2,4] | [3] | 4 |
5 | [3] | [1] | 2 |
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
import Foundation
func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
if lost == reserve { // 여분의 체육복을 가져온 학생이 모두 도난 당한 경우
return n
}
// 여분의 체육복을 가져온 학생이 도난 당한 경우를 위해 두 배열의 중복값 제거
var lostStudents: [Int] = lost.filter{!reserve.contains($0)}.sorted()
var overplusStudents: [Int] = reserve.filter{!lost.contains($0)}.sorted()
for stu in overplusStudents {
if lostStudents.isEmpty { // 도난 당한 학생들이 체육복을 전부다 빌리면 reserve를 읽을 필요가 없다
break
}
if lostStudents.contains(stu - 1) { // 앞 번호에게 빌려주는 경우
let number = lostStudents.firstIndex(of: stu - 1) ?? -1
lostStudents.remove(at: number) // 도난 목록에서 제거
continue
}
if lostStudents.contains(stu + 1) { // 뒷 번호에게 빌려주는 경우
let number = lostStudents.firstIndex(of: stu + 1) ?? -1
lostStudents.remove(at: number) // 도난 목록에서 제거
}
}
return n - lostStudents.count // (전체학생 수 - 도난당했는데 빌리지 못한 경우)
}
이번 문제의 카테고리는 그리디(greedy)
알고리즘이다. 그리디 알고리즘은 매 순간 최선의 선택을 하는 알고리즘이므로 문제에서 최선의 선택인지 무엇인지 알아내는 것이 중요하다.
문제에서 여분의 체육복을 가져온 학생은 도난당한 학생에게 체육복을 빌려줄 수 있다. 그러나 앞뒤 번호(4번은 3번 또는 5번에게만 가능
)인 학생에게만 빌려줄 수 있기 때문에 우리가 고민해야 할 점은 어떤 번호의 학생에게 먼저 체육복을 빌려주는 것이 최선의 선택인지 확인하는 것이다.
어떤 경우가 최선의 선택일까??
정답은 두 가지 경우 모두 최선의 선택이다. 즉 앞의 번호에게 먼저 빌려주거나 아니면 뒷 번호에게 먼저 빌려주거나 상관없이 빌려주는 순서만 일치하면 된다. 여기서 말하는 순서란 어떤 학생은 뒷 번호에게 먼저 빌려주는데 다른 학생은 앞 번호에게 먼저 빌려주는 것이 아닌, 한 학생이 뒷번호에게 먼저 빌려주었다면 다른 학생 모두가 뒷번호에게 먼저 빌려주어야 한다는 뜻이다. 이를 규칙으로 표현하면 다음과 같다
여분의 체육복을 가져온 모든 학생들은 다음 규칙을 중 1개를 따라야 한다.
이번 글에서는 규칙 2번을 따르는 코드를 소개한다. 그러나 글의 후반부에 규칙1 의 코드도 같이 기술하니 참고하길 바란다.
그러면 코드를 살펴본다.
if lost == reserve { // 여분의 체육복을 가져온 학생이 모두 도난 당한 경우
return n
}
문제의 제한사항 마지막을 보면 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
라는 조건이 있다. 그러므로 여분의 체육복을 가져온 학생과 도난당한 학생이 모두 일치한다면 전체 학생의 수를 반환하면 된다.
다음으로 여분의 체육복을 가져온 학생들과 잃어버린 학생들을 정렬하는 코드이다.
var lostStudents: [Int] = lost.filter{!reserve.contains($0)}.sorted()
var overplusStudents: [Int] = reserve.filter{!lost.contains($0)}.sorted()
정렬을 하는 이유는 다음 예시를 보면 이해할 수 있다.
6, [2, 4, 5], [3, 1, 6]
의 예를 보면 만약 3번 학생이 2번 학생에게 먼저 체육복을 빌려주었다고 하자 그러면 1번 학생은 2번의 학생에게 체육복을 빌려줄 수 있음에도 불구하고 못 빌려주는 상황이 발생한다. 4번의 학생은 3번의 학생에게 체육복을 빌릴 수 있는데 받지 못하는 상황이 되므로 이 경우는 그리디 알고리즘을 만족하지 못한다. 그러므로 데이터를 정렬하여 빌려주는 순서를 통일시킨다.
또한 여기서 filter
메소드를 사용하여 중복을 두 배열사이의 공통 값을 제거하는 것을 확인할 수 있다. 이는 여분의 학생이 도난당한 경우 다른 학생에게 체육복을 빌려줄 수 없다는 제한사항을 만족시키기 위해 필요하다.
체육복을 빌려주는 과정이다.
for stu in overplusStudents {
if lostStudents.isEmpty { // 도난 당한 학생들이 체육복을 전부다 빌리면 reserve를 읽을 필요가 없다
break
}
if lostStudents.contains(stu - 1) { // 앞 번호에게 빌려주는 경우
let number = lostStudents.firstIndex(of: stu - 1) ?? -1
lostStudents.remove(at: number) // 도난 목록에서 제거
continue
}
if lostStudents.contains(stu + 1) { // 뒷 번호에게 빌려주는 경우
let number = lostStudents.firstIndex(of: stu + 1) ?? -1
lostStudents.remove(at: number) // 도난 목록에서 제거
}
}
먼저 매 루프마다 여분의 체육복을 가져온 학생 번호를 얻는다. 그 학생은 먼저 앞 번호의 학생에게 체육복을 빌려주고 빌려주지 못한 경우 뒷번호의 학생에게도 빌려주기를 시도한다. 빌려주는 방식은 배열에서 원소 값을 삭제하는 방식으로 표현한다.
마지막으로 결과를 반환하는 코드이다.
return n - lostStudents.count // (전체 학생 수 - 도난당했는데 빌리지 못한 경우)
체육복을 도난당한 학생들을 담는 배열 lostStudents
은 현재 도난당했는데 체육복을 빌리지 못한 학생들이 남아있다. 그러므로 전체 학생 수에서 해당 배열의 element 수를 빼어 반환한다.
해당 코드는 뒷번호의 학생에게 먼저 체육복을 빌려주는 방식으로 접근하는 코드이다.
import Foundation
func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
if lost == reserve { // 여분의 체육복을 가져온 학생이 모두 도난 당한 경우
return n
}
// 여분의 체육복을 가져온 학생이 도난 당한 경우를 위해 두 배열의 중복값 제거
var lostStudents: [Int] = lost.filter{!reserve.contains($0)}.sorted(by: >)
var overplusStudents: [Int] = reserve.filter{!lost.contains($0)}.sorted(by: >)
for stu in overplusStudents {
if lostStudents.isEmpty { // 도난 당한 학생들이 체육복을 전부다 빌리면 reserve를 읽을 필요가 없다
break
}
if lostStudents.contains(stu + 1) {
let number = lostStudents.firstIndex(of: stu + 1) ?? -1
lostStudents.remove(at: number) // 도난 목록에서 제거
continue
}
if lostStudents.contains(stu - 1) {
let number = lostStudents.firstIndex(of: stu - 1) ?? -1
lostStudents.remove(at: number) // 도난 목록에서 제거
}
}
return n - lostStudents.count // (전체학생 수 - 도난당했는데 빌리지 못한 경우)
}
규칙2을 사용한 풀이와 순서와 정렬의 방향만 바꾸면 된다.