[Swift] [40일차] 2799_LEET

LEETCODE 2799

프로그래머스로 제출 시 상단 코드를 좀 참고했었는데, 어떤 코드가 좀 더 뭐가 더 효율적인 코드인지 한눈에 비교하기 위해서 이제는 아마 LEETCODE문제도 병행할 듯 싶다.

---

문제설명

1. 자연수 배열 주어짐
2. 주어진 배열에서 조건을 충족하는 subarray return
3. 조건은 각 element 종류 충족하면 가능
4. 그렇게 만들 수 있는 연속된 subArray의 가지 수 출력 !

---

문제 접근

1. 이게 종류로 따지는거니까 그냥 SET쓰면 되지않을까? 싶었다

 func countCompleteSubarrays(_ nums: [Int]) -> Int {
    let category_cnt = Set(nums).count
    var answer = 0
    var current_length = nums.count
    while current_length >= 1 {
        var stack = [Int]()
        for i in 0 ..< nums.count {
            stack.append(nums[i])
            if stack.count == current_length { // 길이는 찼어
                if Set(stack).count == category_cnt { // 종류도 OK
                    answer += 1
                }
                stack.removeFirst()
            }
        }
        current_length -= 1
    }

    return answer
}

1. 그니까 길이를 배열전체길이부터 시작해서 하나씩 줄여가나면서 슬라이딩 윈도우 느낌?으로 처리를 해줬다.
2. 그래서 current_length는 계속 줄여가면서 길이가 충족하고 , set.count도 충족을 하면 이제 +1 해주는 방식이고 실제 예제도 다 맞았는데...

1058 / 1074 testcases passed

TIME LIMIT이 떴다. 아마 이거 배열을 앞에서 짤라주는 방식이 좀 오래걸려서 그런게 아닐까 싶어서 이부분을 딕셔너리로 한 번 변경을 해봐야겠다..

import Foundation

func countCompleteSubarrays(_ nums: [Int]) -> Int {
    let category_cnt = Set(nums).count
    var answer = 0
    var current_length = nums.count
    while current_length >= 1 {
        for i in 0 ... nums.count - current_length {
            var dict = [Int: Int]()
            for j in i ..< i + current_length {
                dict[nums[j], default: 0] += 1

//                print(dict.reduce(into: 0) { $0 += $1.value })
                if dict.reduce(into: 0) { $0 += $1.value } == current_length { // 길이는 찼어
                    if (dict.filter { $0.value != 0 }.count == category_cnt) {
//                        print(dict)
                        answer += 1
                    }
                    dict[nums[i]]! -= 1
                }
            }
        }
        current_length -= 1
    }

    return answer
}

1013 / 1074 testcases passed

이거는 더 통과를 못했따. 아마 reduce해주고 filter해주는 부분이 좀 오래 소요된 것 같다...

3. 그러면 딕셔너리까지는 오케이!!! 이제 여기서 reduce나 filter안쓰려면 좀 어떻게 축소할 수 있을까? 하다가 다르게 생각을 하게 됐다.

지금까지는 최적으로 해당 종류를 가지는 최소배열을 구하는 것처럼 해줬는데 그게 아니라
일단 확보해둔 배열에서 뒤에는 뭐가 들어와도 되는 거니까 그걸 카운팅해주는 느낌으로 카운팅을 해줬다.

import Foundation

func countCompleteSubarrays(_ nums: [Int]) -> Int {
    let categoryCount = Set(nums).count
    var left = 0
    var answer = 0
    var dict: [Int: Int] = [:]

    for right in 0 ..< nums.count {
        dict[nums[right], default: 0] += 1

        while dict.keys.count == categoryCount { // 종류는 다 채웠고 ~
            answer += nums.count - right // 거기까지 다 됐으니까 이제 right부터 nums.count까지 하나추가할대마다 다 완성배열이니까 그만큼 더해주는 것
            dict[nums[left], default: 0] -= 1 // 이제 시작 자리 옮겨야하니까 -1
            if dict[nums[left]] == 0 {
                dict.removeValue(forKey: nums[left])
            }
            left += 1 // 이제 left부터 시작하는거 다 봤으니 그 다음부터 봐주세요~라는뜻
        }
    }

    return answer
}

[5,5,5,5] 예시

right = 0: [5], [5, 5], [5, 5, 5], [5, 5, 5, 5]
right = 1: [5, 5], [5, 5, 5], [5, 5, 5, 5]
right = 2: [5, 5, 5], [5, 5, 5, 5]
right = 3: [5, 5, 5, 5]

Accepted

1074 / 1074 testcases passed

---

항상 까먹었는 것 같은데 이렇게 subArray같은거로 시간초과로 장난치는 문제들은 다음부터 좀 left,right생각을 해줘야겠다고 생각하게 되었다.