[프로그래머스] 체육복(Kotlin)

[프로그래머스] 체육복(Kotlin)

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

• 주의해야 할 제한 사항:

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

풀이

• 참고) C++ 풀이: [프로그래머스] 체육복

• 여벌의 체육복을 가져온 학생 중 체육복을 도난당한 학생이 있을 수 있음
  -> 정답 != 총 학생 수 - 체육복을 도난당한 학생 수 + 체육복을 빌릴 수 있는 최대 학생 수
  -> 정답 = 체육복을 빌리지 않아도 되는 학생 수 + 체육복을 빌릴 수 있는 최대 학생 수

import kotlin.math.*

class Solution {
    //체육복을 빌릴 수 있는 가장 많은 학생의 수
    fun getMaxBorrow(start:Int, state: Array<Int>):Int{
        if(start >= state.size) return 0
            
        var result = 0
        for(i in start until state.size){
            if(state[i] != 0) continue
            
            //(1)체육복을 빌리지 않는 경우
            result = max(result, 0 + getMaxBorrow(i + 1, state))
            
            //(2)자신의 앞에 있는 학생에게 체육복을 빌린 경우
            if((i > 0) &&(state[i] == 0)&&(state[i-1] == 2)){
                state[i-1] = 1
                state[i] =1
                result = max(result, 1 + getMaxBorrow(i + 1, state))
                state[i-1] = 2
                state[i] = 0
            }
            
            //(3)자신의 뒤에 있는 학생에게 체육복을 빌린 경우
            if((i < state.size - 1) &&(state[i] == 0)&&(state[i+1] == 2)){
                state[i] =1
                state[i+1] = 1
                result = max(result, 1 + getMaxBorrow(i + 1, state))
                state[i] = 0
                state[i+1] = 2
            }
            
            break
        }
        return result
    }
    
    
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        //전체 학생의 체육복 보유 현황
        //일반 학생의 경우 1, 도난당한 경우 0, 여벌이 있는 경우 2
        var state = Array(n, {it -> 1})
        for(l in lost) state[l-1]--
        for(r in reserve) state[r-1]++
        
        //체육복을 빌리지 않아도 되는 학생의 수
        var okay = 0
        state.forEach{if(it != 0) okay++}
        
        //체육복을 빌릴 수 있는 가장 많은 학생의 수
        var maxBorrow = getMaxBorrow(0, state)
        
        val answer = okay + maxBorrow
        return answer
    }
}