체육복

LEEHAKJIN-VV·2022년 6월 15일
0

프로그래머스

목록 보기
25/37

출처: 프로그래머스 코딩 테스트 연습

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 전체 학생의 수는 2명 이상 30명 이하입니다.
  • 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
  • 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

nlostreservereturn
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개를 따라야 한다.
이번 글에서는 규칙 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을 사용한 풀이와 순서와 정렬의 방향만 바꾸면 된다.

0개의 댓글