03/06 알고리즘 공부(64) - 체육복

조건

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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

알고리즘 예상

1. lost의 원소들을 대상으로 lost[i]+1, lost[i]-1 의 번호가 reserve에 있는 지 검사
2. 해당하는 번호 중 낮은 번호를 배열 attend에 저장(1번 예시처럼 lost 하나에 두 reserve가 대응할 수 있기 때문)
   1. 낮은 번호가 attend에 존재하면 높은 번호 저장
3. 중복제거(2번 예시처럼 reserve 하나에 lost 2개가 대응하므로)
4. n - lost.size + (attend의 원소 중 0이 아닌 값의 개수)의 값을 answer에 저장 후 

 

초기 코드

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = 0
        return answer
    }
}

 

내 코드

//실패한 코드
class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = 0
        var attend = IntArray(lost.size)
        
        for(i in lost.indices){
            var bigger: Int = 0
            var smaller: Int = 0
            if(reserve.contains(lost[i]+1)) bigger = lost[i]+1
            if(reserve.contains(lost[i]-1)) smaller = lost[i]-1
            if(attend.contains(smaller)) attend[i] = bigger
            else attend[i] = smaller
        }
        answer = n - lost.size + attend.toList().distinct().count{ it != 0 }
        return answer
    }
}

제한사항에 있는 마지막 조건을 보지 못했다. lost와 reserve에 동시에 있는 원소에 대해 처리할 필요가 있다.

//실패한 코드
class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = 0
        var attend = IntArray(lost.size)
        
        for(i in lost.indices){
            var bigger: Int = 0
            var smaller: Int = 0
            if(reserve.contains(lost[i])){
                attend[i] = lost[i]
            }
            else{
                if(reserve.contains(lost[i]+1)) bigger = lost[i]+1
                if(reserve.contains(lost[i]-1)) smaller = lost[i]-1
                if(attend.contains(smaller)) attend[i] = bigger
                else attend[i] = smaller
            }
        }
        answer = n - lost.size + attend.toList().distinct().count{ it != 0 }
        return answer
    }
}

조건문을 이용해 여분 체육복을 가지고 온 사람이 도둑 맞았을 때에 대해 처리했다. 이럼에도 실패한것으로 보아 생각했던 알고리즘 자체에 문제가 있는 것 같다.
문제를 찾았다. 위 방법은 lost가 오름차순일 때만 적용된다.

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = 0
        var attend = IntArray(lost.size)
        val lostSorted = lost.sorted()
        for(i in lost.indices){
            var bigger: Int = 0
            var smaller: Int = 0
            if(reserve.contains(lostSorted[i])) {
                attend[i] = lostSorted[i]
            }else {
                if(reserve.contains(lostSorted[i]+1)) bigger = lostSorted[i]+1
                
                if(reserve.contains(lostSorted[i]-1)) smaller = lostSorted[i]-1
                
                if(attend.contains(smaller)) {
                    attend[i] = bigger
                }else {
                    attend[i] = smaller
                }
            }
        }
        answer = n - lost.size + attend.toList().distinct().count{ it != 0 }
        return answer
    }
}

lostSorted라는 변수를 선언해 해결했다. 생각해본 다른 방법으로는 크기가 n인 배열 student를 이용하는 방법인데 lost의 원소를 빼고 원소가 0인 부분에서 위와 비슷하게 bigger, smaller, 같은 번호 검사를 적용하고 reserve에서 원소를 빼는 방법도 있을 것 같다.

다른 사람의 풀이

class Solution {
        fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {

            var answer = n
            var lostSet = lost.toSet() - reserve.toSet()
            var reserveSet = (reserve.toSet() - lost.toSet()) as MutableSet

            for (i in lostSet) {
                when {
                    i + 1 in reserveSet -> reserveSet.remove(i + 1)
                    i - 1 in reserveSet -> reserveSet.remove(i - 1)
                    else -> answer--
                }
            }
            return answer
        }
}

이 풀이는 좀 예전 풀이라 정렬 관련해서 구현이 되어있지 않지만  Set을 이용해 풀었다.

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = n

        for(i in lost){
            var prev = i - 1
            var next = i + 1

            if(reserve.contains(i)){
               reserve.set(reserve.indexOf(i), -1)
                continue
            }
            else if(reserve.contains(prev)){
               reserve.set(reserve.indexOf(prev), -1)
               continue
            }else if(reserve.contains(next)){
               reserve.set(reserve.indexOf(next), -1)
               continue
            }
            answer--
        }
        return answer
    }
}

이 풀이의 경우에는 있는지 검사를 해 없다면 answer--를 하는 방법을 사용했다. 이 풀이 역시 정렬 관련한 내용이 빠져있다.

개선점 또는 배운점

1. 중복검사를 set을 이용해 하는 방법을 알면서도 쓸 생각을 못했다. 
2. 최근 알고리즘 문제를 풀 때 연산이 많아 상당히 지저분하다. 의사코드를 고민할 때 사용할 방법에 대해 좀 더 고민을 할 필요가 있어보인다.

 

개선된 코드

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = 0
        var attend = mutableSetOf<Int>(0)
        val lostSorted = lost.sorted()
        for(i in lost.indices){
            var bigger: Int = 0
            var smaller: Int = 0
            if(reserve.contains(lostSorted[i])) {
                attend.add(lostSorted[i])
            }else {
                if(reserve.contains(lostSorted[i]+1)) bigger = lostSorted[i]+1
                
                if(reserve.contains(lostSorted[i]-1)) smaller = lostSorted[i]-1
                
                if(attend.contains(smaller)) {
                    attend.add(bigger)
                }else {
                    attend.add(smaller)
                }
            }
        }
        answer = n - lost.size + attend.count() - 1
        return answer
    }
}

attend의 초기값에 0을 넣어 최초 반복 시 set에 0을 넣지 않도록 하고 answer 값을 계산할 때 1을 빼주었다.