Algorithm / 롤케이크 자르기

문제

프로그래머스 / 롤케이크 자르기

1) 문제 풀이

import Foundation

func solution(_ topping:[Int]) -> Int {
    var answer = 0
    var slice: Set<Int> = []
    var arr = topping
    
    while !arr.isEmpty {
        slice.insert(arr.removeFirst())
        
        if slice.count == Set(arr).count {
            answer += 1
        }
    }
        
    return answer
}

결과

2) 코드 개선

⚠️ 문제점 분석

• 시간복잡도 문제
  • 현재 시간 복잡도는 removeFirst() = O(n) * Set(arr) = O(n) = O(N²)으로 매우 비효율적

✅ 개선 포인트

• Dictionary를 활용
  • 미리 왼쪽부터의 토핑 종류 개수와 오른쪽부터의 토핑 종류 개수를 계산하면서 비교
  • 딕셔너리(Map)과 Set을 사용해 중복 없이 관리

func solution(_ topping: [Int]) -> Int {
    var answer = 0
    var left: [Int: Int] = [:]
    var right: [Int: Int] = [:]

    // 초기에는 모든 토핑을 right에 넣는다
    for t in topping {
        right[t, default: 0] += 1
    }

    for t in topping {
        // 왼쪽에 토핑 추가
        left[t, default: 0] += 1

        // 오른쪽에서 해당 토핑 제거
        right[t]! -= 1
        if right[t]! == 0 {
            right.removeValue(forKey: t)
        }

        // 서로 다른 토핑 개수가 같으면 answer 증가
        if left.count == right.count {
            answer += 1
        }
    }

    return answer
}

결과