Algorithm / 할인 행사

문제

프로그래머스 / 할인 행사

1) 문제 풀이

func solution(_ want:[String], _ number:[Int], _ discount:[String]) -> Int {
    
    var wantDic: [String: Int] = [:]
    var index: Int = 0
    var answer: Int = 0
    
    for j in want {
        if !discount.contains(j) {
            return 0
        }
    }
    
    for i in 0..<want.count {
        wantDic[want[i], default: 0] = number[i]
    }
    
    while (index + 9) < discount.count {
        var dic: [String: Int] = [:]
        
        for i in index...(index + 9) {
            dic[discount[i], default: 0] += 1
        }
        
        for (i, w) in want.enumerated() {
            if dic[w] == wantDic[w] {
                if i == (want.count - 1) {
                    answer += 1
                    break
                }
                continue
            } else {
                break
            }
        }
        
        index += 1
    }
    
    return answer
}

결과

2) 코드 개선

⚠️ 문제점 분석

• 매 슬라이딩 윈도우마다 새 딕셔너리를 만들고 그 안에서 want 전체를 순회
  • 이중 루프에 가까운 구조 -> O(n*m), n: discont, m: want
  • 비교 방식도 불안정: want[i]가 딱 필요한 만큼 있어도, Index가 다르면 통과 못 할 수도 있음
  • 개선: dic == wantDic으로 비교하면 더 정확하고 간결(단, 성능을 고려하면 해시 기반 비교로 최소화 해야함)
• 반복 종료 조건
  • while (index + 9) < discount.count 형식에 문제는 없지만 가독성이 나쁨
  • while index <= discount.count - 10이 좀 더 명확함

✅ 개선 포인트

• 매번 윈도우를 구성할 때 딕셔너리를 만들어 wantDic과 비교
• 성능을 고려해 슬라이딩 윈도우는 O(n) 방식으로 순차 이동

func solution(_ want:[String], _ number:[Int], _ discount:[String]) -> Int {
    var answer = 0
    let wantDic = Dictionary(uniqueKeysWithValues: zip(want, number))
    let totalDays = 10
    
    for i in 0...(discount.count - totalDays) {
        let window = discount[i..<i + totalDays]
        var countDic: [String: Int] = [:]
        
        for item in window {
            countDic[item, default: 0] += 1
        }

        if countDic == wantDic {
            answer += 1
        }
    }

    return answer
}

결과