[Algorithms] 할인 행사

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

프로그래머스

 

자! 풀이가 바로 나와야 하는데, 물론 내 머리에서는 바로 안 나와요.

그래서 맨날 코딩 테스트에서 떨어지나 봐요. ㅎ

한 10분 고민하다 제가 선택한 방법은 바로 "슬라이딩 윈도우"

슬라이딩 윈도우가 뭐냐?

슬라이딩 윈도우는 말 그대로 "창문을 슬슬 옮기면서 본다"라는 뜻인데, 배열에서 일정 구간을 계속 확인해야 할 때 사용하는 방법입니다! 내가 이걸 왜 아냐? 코테에서 나온 적 있음! 물론 떨어졌음ㅎ

여기서는 10일 동안 할인되는 제품을 확인해야 하니까, 10개의 아이템을 하나의 '창문'으로 보고, 이 창문을 하루씩 옆으로 밀면서 (즉, 슬라이딩하면서) 조건을 체크하는 방식으로 푸는 거죠.

 

코드 먼저 투척하겠다!

import Foundation

func solution(_ want: [String], _ number: [Int], _ discount: [String]) -> Int {
    var result = 0
    
    // discount 배열의 길이가 10 미만이면 0을 반환
    guard discount.count >= 10 else { return 0 }
    
    // 슬라이딩 윈도우로 10일씩 확인
    for i in 0...(discount.count - 10) {
        var isPossible = true
        
        // 각 want와 number에 대해 10일간의 할인 목록에서 원하는 개수가 있는지 확인
        for j in 0..<want.count {
            let currentItem = want[j]
            let currentItemCount = number[j]
            
            // 10일간 해당 제품의 개수 계산
            let discountSlice = discount[i..<(i+10)]
            if discountSlice.filter({ $0 == currentItem }).count < currentItemCount {
                isPossible = false
                break
            }
        }
        
        // 원하는 조건을 만족하는 경우 결과값 증가
        if isPossible {
            result += 1
        }
    }
    
    return result
}

 

하나씩 차근차근 뜯어볼까요?

자, discount의 길이가 10 이하면? 문제가 잘못된 거죠 0 반환하면 됨ㅇㅇ

그러고 나서 슬라이딩 윈도 기법으로 푼다고 했잖아요?

그럼 discount [0] ~ discount [9]을 한번 슥- 보는 거죠

조건이 맞지 않다? 그러면 그다음으로 discount [1] ~ discount [10]을 보는 거고 또 맞지 않다? discount [2] ~ discount [11]을 보는 이런 방식입니다!

 

    // 슬라이딩 윈도우로 10일씩 확인
    for i in 0...(discount.count - 10) {

이 부분이 핵심임. 우리는 할인 목록인 discount에서 10일 구간을 하나씩 밀면서 확인할 건데. 그래서 i는 0부터 discount.count - 10까지 반복됩니다. 왜 -10이냐면, 만약 discount.count가 14라면 5번째에서 10일을 확인해야 하니까 그 범위를 맞춰주기 위함입니다. 나머지 코드 더 보면 이해 갈 거임.

var isPossible = true

 

이건 트리거라고 보시면 됩니다. 이번 10일 구간이 조건을 만족하는지 아닌지.

 

        // 각 want와 number에 대해 10일간의 할인 목록에서 원하는 개수가 있는지 확인
        for j in 0..<want.count {
            let currentItem = want[j]
            let currentItemCount = number[j]

 

이제 정현이가 원하는 제품과 수량을 하나씩 확인하는데, want [j]는 정현이가 원하는 제품 이름이고, number [j]는 그 제품을 몇 개 사고 싶은지를 나타냅니다.

 

            // 10일간 해당 제품의 개수 계산
            let discountSlice = discount[i..<(i+10)]

discount [i..<(i+10)]는 discount 배열에서 i번째부터 i+9번째까지 10일간의 제품 리스트를 잘라낸 부분!

이 구간에서 정현이가 원하는 제품이 몇 개나 있는지 확인!

 

            if discountSlice.filter({ $0 == currentItem }).count < currentItemCount {
                isPossible = false
                break
            }

이제 filter를 사용해서 discountSlice에서 정현이가 원하는 제품이 몇 개 있는지 세요.

만약 정현이가 원하는 수량만큼 없으면, 이번 구간은 조건을 만족하지 못하니까 isPossible = false로 바꾸고 더 이상 확인할 필요 없이 break로 빠져나옴.

 

마지막으로 모든 want 항목이 조건을 만족하면 isPossible은 여전히 true일 테니. 그럼 result 값을 하나 늘려줍니다. 이 과정을 discount 배열의 모든 10일 구간에 대해 반복하고, 마지막에 result를 반환합니다.

 

정리하자면

 

• 10일씩 구간을 슬라이딩하면서 확인한다.
• 각 구간에서 정현이가 원하는 제품이 필요한 수만큼 있는지 확인한다.
• 조건을 만족하면 result 값을 늘려서 조건을 만족하는 구간이 몇 개인지 세서 반환한다.

고작 레벨2 푸는데 45분 걸렸다.

시간 줄이는 연습도 필요한 것 같다.