[Swift Algorithm] 체육복 Programmers(Lv.1)

문제 설명

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

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

 

제한 조건

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

 

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

 

내 문제 풀이

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var student = Array<Int>(repeating: 1, count: n)
    var result = 0
    
    for i in 0..<lost.count {
        student[lost[i]-1] -= 1
    }
    for i in 0..<reserve.count {
        student[reserve[i]-1] += 1
    }

    if student[0] == 0 && student[1] == 2 {
        student[0] = 1
        student[1] = 1
    }
    if student[n-1] == 0 && student[n-2] == 2 {
        student[n-1] = 1
        student[n-2] = 1
    }
    
    if n > 2 {
        for i in 1..<n-1 {
            if student[i] == 0 {
                if student[i-1] == 2 {
                    student[i] = 1
                    student[i-1] = 1
                }
                else {
                    if student[i+1] == 2 {
                        student[i] = 1
                        student[i+1] = 1
                    }
                }
            }
        }
    }
    
    for i in 0..<n {
        if student[i] == 0 {
            result += 1
        }
    }
    
    return n - result
}

• 먼저 학생 수 크기의 배열을 생성하고, 1씩 저장해주었다.
• 그 다음 체육복을 잃어버린 학생은 -1, 여분이 있는 학생은 +1 해주었다. (맨 위 for문 두 개)
• 그리고 이제 체육복을 분배할 차례인데, 우선 맨 앞 학생과 맨 뒤 학생만 예외로 처리해주었다.
  (맨 첫 번째 학생이 체육복이 없고, 그 다음 학생이 여벌이 있을 경우,
  그리고 맨 뒤 학생이 체육복이 없고, 그 전 학생이 여벌이 있을 경우!)
• 그리고 학생 수가 3명 이상일 경우 for문으로 체육복을 배분했다.
  (2명 이하일 경우 위의 예외 처리들로 분배 가능하기 때문!)
• for문은 배열의 1부터 n-2까지 반복해주었다. (0, n-1은 위에서 처리했기 때문)
• for문 안에서는 만약 student 배열의 i 번째 학생이 0일 경우 앞, 뒤 학생이 여벌을 갖는지 확인했다.
• 먼저 앞 학생이 여벌이 있다면 (2 라면) 그 학생에게 빌리고, 앞 학생이 여벌이 없고 뒤 학생이 있다면 빌려주었다.
• 위와 같은 방식으로 진행한 후, for문을 이용해 배분이 끝났음에도 체육복이 없는 학생 수를 구했다.
• 전체 학생 수에서 체육복이 없는 학생 수를 빼주어 반환했다.

 

인상적인 풀이

import Foundation

func solution(_ n: Int, _ lost: [Int], _ reserve: [Int]) -> Int {
    let newReserve = reserve.filter { !lost.contains($0) }
    let newLost = lost.filter { !reserve.contains($0) }

    var lostPeople: Int = newLost.count

    newReserve.forEach {
        let isLend: Bool = newLost.contains($0 - 1) || newLost.contains($0 + 1)
        if isLend && lostPeople > 0 {
            lostPeople -= 1
        }
    }

    return n - lostPeople
}

• 먼저 filter를 사용하여 여벌이 있는 학생 중 도난 당하지 않은 학생들로 newReserve 배열을 생성, 
  도난당한 학생들 중 여벌이 없는 학생들로 newLost 배열을 생성해주었다.
• 여벌 없이 잃어버린 학생들의 명수를 lostPeople에 저장했다.
• newReserve에 forEach를 사용해 반복해주었고,
  newReserve의 학생의 앞, 뒤 학생이 newLost 배열에 포함되는 학생인지 검사한다.
• 만약 검사 결과가 true이면서 체육복이 없는 학생이 1명 이상일 경우 lostPeople에서 한 명을 빼주는 것을 반복한다.
• 마지막으로 전체 학생 수에서 체육복이 없는 학생 수를 빼주어 반환했다.

 

💡 피드백

• filter와 contains를 적절히 사용하여 정말 효과적인 코드를 작성한 것,, 너무 대단하다
• 나도 다양한 함수를 많이 사용해보며 더욱 간결하게 코드를 작성할 수 있도록 연습해야겠다,,

 

---

 

🖍 [ 추가 ] 1주일 후 다시 풀어보기

func solution2(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var stu = Array(repeating: 1, count: n)
    for i in 0..<lost.count { stu[lost[i]-1] -= 1 }
    for i in 0..<reserve.count { stu[reserve[i]-1] += 1 }
                             
    if stu[0]==0 && stu[1]==2 { stu[0]=1; stu[1]=1 }
    if stu[n-1]==0 && stu[n-2]==2 {stu[n-1]=1; stu[n-2]=1}

    for i in 1..<n-1 {
        if stu[i]==0 {
            if stu[i-1]==2 { stu[i-1]=1; stu[i]=1 }
            else if stu[i+1]==2 { stu[i]=1; stu[i+1]=1 }
        }
    }
    
    return stu.filter({$0 > 0}).count
}

• 학생 수만큼 1을 채운 배열을 만들어준 후 잃어버린 학생은 -1, 여분이 있는 학생은 +1 해주었다.
• 첫 번째 학생이 체육복이 없는 상황과 마지막 학생이 체육복이 없는 상황은 따로 빼서 해결했다.
• for문에서는 [1]번째 학생부터, 체육복이 없다면 이전 학생에게 우선, 안되면 뒤 학생에게 빌리는 식으로 작성했다.
• filter 사용하여 체육복을 한 개 이상 가지게 된 학생들의 수를 출력했다.
• 첫 번째 풀이보다 훨씬 간결하게 잘 작성한듯 하다!!

 

---

 

문제

https://programmers.co.kr/learn/courses/30/lessons/42862