[LeetCode][Kotlin] 2483. Minimum Penalty for a Shop

2483. Minimum Penalty for a Shop

You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':

• if the ith character is 'Y', it means that customers come at the ith hour
• whereas 'N' indicates that no customers come at the ith hour.

If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows:

• For every hour when the shop is open and no customers come, the penalty increases by 1.
• For every hour when the shop is closed and customers come, the penalty increases by 1.

Return the earliest hour at which the shop must be closed to incur a minimum penalty.

Note that if a shop closes at the jth hour, it means the shop is closed at the hour j.

문자 'N'과 'Y'로만 구성된 0-인덱스 문자열 고객으로 표시되는 상점의 고객 방문 로그가 제공됩니다.
- i번째 문자가 'Y'이면 고객이 i번째 시간에 온다는 의미입니다. 
- 반면 'N'은 i번째 시간에 고객이 오지 않음을 나타냅니다. 

상점이 j번째 시간(0 <= j <= n)에 문을 닫는 경우 벌금은 다음과 같이 계산됩니다. 
- 상점이 열려 있고 손님이 없을 때마다 페널티가 1씩 증가합니다. 
- 가게가 문을 닫고 손님이 올 때마다 페널티가 1씩 증가합니다. 

최소 벌금이 부과되기 위해 상점이 문을 닫아야 하는 가장 빠른 시간을 반환하세요. 

상점이 j시간에 문을 닫는다면 상점은 j시간에 문을 닫는다는 의미입니다.

 

Example 1:

Input: customers = "YYNY"

Output: 2

Explanation: 

- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.

- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.

- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.

- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.

- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.

Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

 

Example 2:

Input: customers = "NNNNN"

Output: 0

Explanation: It is best to close the shop at the 0th hour as no customers arrive.

 

Example 3:

Input: customers = "YYYY"

Output: 4

Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.

 

Constraints:

• 1 <= customers.length <= 10^5
• customers consists only of characters 'Y' and 'N'.

---

코드 1

class Solution {
    fun bestClosingTime(customers: String): Int {
        var score = customers.count { it == 'Y' }
        if (score == customers.length) return customers.length

        val hm = hashMapOf(0 to score)

        (1..customers.length).forEach { i ->
            if (customers[i - 1] == 'Y') {
                score--
            } else {
                score++
            }
            hm[i] = score
        }

        return hm.entries.sortedWith(compareBy({ it.value }, { it.key })).first().key
    }
}

 

코드 2

class Solution {
    fun bestClosingTime(customers: String): Int {
        val N = customers.length
        val prefix = IntArray(N + 1)
        val postfix = IntArray(N + 1)

        for (i in 1..N) {
            prefix[i] = prefix[i - 1] + if (customers[i - 1] == 'N') 1 else 0
        }

        for (i in N - 1 downTo 0) {
            postfix[i] = postfix[i + 1] + if (customers[i] == 'Y') 1 else 0
        }

        var res = Integer.MAX_VALUE
        var min = Integer.MAX_VALUE
        for (i in 0..N) {
            val pen = prefix[i] + postfix[i]
            if (pen < min) {
                min = pen
                res = i
            }
        }

        return res
    }
}

 

코드 3

class Solution {
    fun bestClosingTime(customers: String): Int {
        var cur = 0
        var max = 0
        var closeTime = 0

        for ((i, c) in customers.withIndex()) {
            cur += if (c == 'Y') 1 else -1
            if (cur > max) {
                max = cur
                closeTime = i + 1
            }
        }

        return closeTime
    }
}

 

코드 4

class Solution {
    fun bestClosingTime(customers: String): Int {
        var answer = 0
        var p = customers.count { it == 'Y' }
        var min = p

        for (i in 1..customers.length) {
            if (customers[i - 1] == 'Y') {
                p--
            } else {
                p++
            }

            if (p < min) {
                min = p
                answer = i
            }
        }

        return answer
    }
}

 

코드 5

class Solution {
    fun bestClosingTime(customers: String): Int {
        val penalty = IntArray(customers.length + 1)

        var sum = 0
        for (i in 1..customers.length) {
            if (customers[i - 1] == 'N') {
                sum++
            }
            penalty[i] = sum
        }

        sum = 0
        for (i in customers.length - 1 downTo 0) {
            if (customers[i] == 'Y') {
                sum++
            }
            penalty[i] += sum
        }

        return penalty.indexOf(penalty.minOrNull()!!)
    }
}