[프로그래머스] 귤 고르기 Swift

 

 

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

프로그래머스

 

1. 처음 코드

처음에는 단순하게, 문제의 아이디어만 가지고 구현에 초점을 두었습니다.
tangerine = [1, 3, 2, 5, 4, 5, 2, 3] 일 때

1. tangerine 배열에 숫자의 빈도수를 딕셔너리로 만든다. (순서 보장 X)
[1: 1, 3: 2, 5: 2, 4: 1, 2: 2]

2. 딕셔너리를 빈도수가 많은 순으로 정렬하고 리스트로 만들어 준다 (딕셔너리는 정렬을 못하기 때문에)
[5, 5, 3, 3, 2, 2, 4, 1]

3. 정렬된 리스트에서 상위 k개를 뽑아낸다.
k = 6 일 때, [5, 5, 3, 3, 2, 2]

4. 해당 리스트를 Set로 만들어 준다.
[5, 3, 2]

5. Set의 개수를 세준다.
3

import Foundation

func solution(_ k: Int, _ tangerine: [Int]) -> Int {

    // 1. 빈도수를 딕셔너리 형태로 만들기
    // O(n)
    let frequency = tangerine.reduce(into: [:]) { counts, number in
        counts[number, default: 0] += 1
    }

    // 2. 빈도수 내림차순, 빈도수가 같을 경우 숫자 내림차순 으로 정렬
    // O(nlogn)
    let sortedArr = tangerine.sorted {
        if frequency[$0]! == frequency[$1]! {
            return $0 > $1 // 빈도수가 같다면 내림 차순
        } else {
            return frequency[$0]! > frequency[$1]!
        }
    }

    // 3, 4, 5 적용
    return Set(sortedArr.prefix(k)).count
}

이런 아이디어로, O(nlogn) 의 시간 복잡도를 가진 코드로 풀 수 있었습니다.

---

2. 개선하기

정답을 풀고 나서, Dictionary의 생성자(grouping)를 사용해서 해결했던 분의 코드를 보고 개선하기로 마음먹었습니다.
저도 grouping 생성자를 활용하기로 했습니다.

해당 생성자를 활용하면, 아래와 같이 쉽게 grouping을 할 수 있습니다.

let tangerine = [1, 3, 2, 5, 4, 5, 2, 3]
let dict = Dictionary(grouping: tangerine) { $0 }
print(dict) [5: [5, 5], 3: [3, 3], 1: [1], 2: [2, 2], 4: [4]]

 

이후에 values만 뽑아서
배열들의 개수로 정렬하고,
flatMap을 통해 배열을 퍼준다음
필요한 만큼 prefix 해준다면

원하는 결과를 얻을 수 있습니다

---

3. 개선된 코드

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    
    let dict = Dictionary(grouping: tangerine) { $0 }.values // [[2, 2], [3, 3], [1], [5, 5], [4]]
        .sorted { $0.count > $1.count } // [[5, 5], [2, 2], [3, 3], [1], [4]]
        .flatMap { $0 } // [5, 5, 2, 2, 3, 3, 1, 4]
        .prefix(k) // [5, 5, 2, 2, 3, 3]

    let resultSetCount = Set(dict).count
    
    return resultSetCount
}

개선하는 과정에서 배열의 개수가 동일한 경우는 따로 순서를 지정 안 해도 된다고 생각했습니다.
(예를 들어 [[5, 5], [2, 2], [3, 3]] 와 [[3, 3], [5, 5], [2, 2]] 입니다.)

실제로 채점 시간도 많이 줄었습니다!

4. Review

개선하는 과정에서 grouping을 활용하여 새로운 Dictionary를 만드는 방법을 학습했습니다.

---

 

티스토리에서 오블완 챌린지라는 것이 생겼습니다. 관심 있으신 분들은 참여하면 좋을 것 같아요!

https://www.tistory.com/event/write-challenge-2024

작심삼주 오블완 챌린지