[Swift 알고리즘] Programmers 할인 행사

○

Level 2 연습문제 (슬라이딩 윈도우)

 

Programmers 할인 행사

 

10일 동안 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 return 하는 문제

 

통과하긴 했지만 무지성으로 풀었긔..

 

슬라이딩 윈도우 사용해서 푸는 법

1. discount 배열을 하루씩 이동하며 길이 10인 slice를 만들어 비교

2. 각 slice마다 해당 기간의 제품 종류와 수량이 want 와 number를 만족하는지 확인

 

func solution(_ want:[String], _ number:[Int], _ discount:[String]) -> Int {
    var result = 0
    
    // 원하는 제품과 수량을 딕셔너리로 변환
    let wantMap = Dictionary(uniqueKeysWithValues: zip(want, number))
    
    // discount에서 10일짜리 윈도우를 슬라이딩
    for i in 0...(discount.count - 10) {
        let slice = discount[i..<i+10]
        var discountMap = [String: Int]()
        
        for item in slice {
            discountMap[item, default: 0] += 1
        }
        
        // 원하는 제품 수량을 만족하는지 검사
        var matched = true
        for (item, qty) in wantMap {
            if discountMap[item, default: 0] != qty {
                matched = false
                break
            }
        }
        
        if matched {
            result += 1
        }
    }
    
    return result
}

 

이렇게 풀면 시간 복잡도는 O(n * m)

- n : 할인 기간 길이 (discount.count)

- m : 원하는 제품 종류 수 (want. count)

고정된 슬라이싱 길이 10일 기준이라 매우 빠르다 (?)

 

 

무지성으로 푼 나의 풀이

func solution(_ want:[String], _ number:[Int], _ discount:[String]) -> Int {
    var result = 0
    
    var wantDict: [String: Int] = [:]
    for i in 0..<want.count {
        wantDict[want[i]] = number[i]
    }
    
    for item in discount[0..<10] {
        if wantDict[item] != nil {
            wantDict[item]! -= 1
        }
        
        if wantDict.values.filter ({ $0 > 0 }).count == 0 {
            result += 1
        }
    }
    
    for (index, item) in discount[10..<discount.count].enumerated() {
        if wantDict[discount[index]] != nil {
            wantDict[discount[index]]! += 1
        }
        
        if wantDict[item] != nil {
            wantDict[item]! -= 1
        }
        
        if wantDict.values.filter ({ $0 > 0 }).count == 0 {
            result += 1
        }
    }
    
    return result
}

뭐.. 처음 10개 값으로 앞뒤로 하나씩 빼고 더하면서 슬라이딩 윈도우 비스무리한 개념으로 풀긴 했지만 조잡하다. 

슬라이딩 윈도우 사용해서 깔끔하게 풀자