Algorithm: 해시 - 베스트앨범

해시 문제 목록 링크 / 문제 링크 / Github 링크

import Foundation

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
     return []
}

문제가 발생한 코드

import Foundation

func solution(_ genres: [String], _ plays: [Int]) -> [Int] {
    let songInfo = Dictionary(uniqueKeysWithValues: zip(genres.indices, zip(genres, plays)))
    let songSorted = songInfo
        .sorted { $0.key < $1.key } 
        .sorted { $0.value.1 > $1.value.1 }
        .sorted { $0.value.0 > $1.value.0 }
    
    var resultAlbum: [Int] = []
    
    var genrePicked1: Set<String> = []
    var genrePicked2: Set<String> = []
    for (key, value) in songSorted {
        let genre = value.0
        if !genrePicked1.contains(genre) {
            resultAlbum.append(key)
            genrePicked1.insert(genre)
        } else if !genrePicked2.contains(genre) {
            resultAlbum.append(key)
            genrePicked2.insert(genre)
        } else { continue }
    }

    return resultAlbum
}

문제 발생

가설 설정

주어진 조건을 모두 달성하는가?

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. ❌
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. ✅
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. ✅
4. 장르별로 노래를 두 개씩 모아 수록합니다. ✅
4'. 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다. ✅

    let songInfo = Dictionary(uniqueKeysWithValues: zip(genres.indices, zip(genres, plays)))
    let songSorted = songInfo
        .sorted { $0.key < $1.key } // 고유 번호 정렬 (조건 3)
        .sorted { $0.value.1 > $1.value.1 } // 재생수 내림차순 정렬 (조건 2)
        .sorted { $0.value.0 > $1.value.0 } // 장르 정렬 (조건 1 미달)
    
    var resultAlbum: [Int] = []
    
    var genrePicked1: Set<String> = []
    var genrePicked2: Set<String> = []
    for (key, value) in songSorted {
        let genre = value.0
        if !genrePicked1.contains(genre) { // 장르 별 한 번 뽑기 (조건 4')
            resultAlbum.append(key)
            genrePicked1.insert(genre)
        } else if !genrePicked2.contains(genre) { // 장르 별 두 번 뽑기 (조건 4)
            resultAlbum.append(key)
            genrePicked2.insert(genre)
        } else { continue }
   }

• 가설: 조건 1이 달성되지 않음.
• 해결 방법: 장르를 재생수 순으로 정렬한 후, 숫자로 치환할 수 있다면 songInfo의 장르에 따른 정렬이 가능
• 구현화: 장르의 재생수 순위를 딕셔너리로 만들면, 그것을 참고해서 정렬이 가능할 것 (예: ["pop": 0, "classic": 1])

가설 검증

    // 빈 딕셔너리 생성
    var totalPlaysByGenre: [String: Int] = [:] 
    
    // 장르별 재생수 취합
    for info in songInfo.values {
        let genre = info.0, plays = info.1
        totalPlaysByGenre[genre, default: 0] += plays
    }
    
    // 취합한 것을 정렬 후 배열로 생성
    let genreByPlays = totalPlaysByGenre
        .sorted(by: { $0.value > $1.value })
        .map({ $0.key })
        
    // (Key: 장르, Value: 장르 순위)인 딕셔너리를 생성
    let genreRank = Dictionary(uniqueKeysWithValues: zip(genreByPlays, genreByPlays.indices))

    let songSorted = songInfo
        .sorted { $0.key < $1.key }
        .sorted { $0.value.1 > $1.value.1 }
        .sorted { genreRank[$0.value.0, default: -1] < genreRank[$1.value.0, default: -1] } // 딕셔너리를 참고해 정렬 (조건 1)

문제 해결

문제를 해결한 코드 (Case A)

import Foundation

func solution(_ genres: [String], _ plays: [Int]) -> [Int] {
	// 곡 정보 (Key: 곡 고유번호, Value: (장르, 재생 수))
    var songInfo = Dictionary(uniqueKeysWithValues: zip(genres.indices, zip(genres, plays)))
    
    // 장르별 재생수 취합
    var totalPlaysByGenre: [String: Int] = [:]
    for info in songInfo.values {
        let genre = info.0, plays = info.1
        totalPlaysByGenre[genre, default: 0] += plays
    }
    let genreByPlays = totalPlaysByGenre
        .sorted(by: { $0.value > $1.value })
        .map({ $0.key })
    
    // 장르 순위 (Key: 장르, Value: 장르 순위)
    let genreRank = Dictionary(uniqueKeysWithValues: zip(genreByPlays, genreByPlays.indices))
    
    // 곡 순위
    let songSorted = songInfo
        .sorted { $0.key < $1.key } // 고유 번호 정렬
        .sorted { $0.value.1 > $1.value.1 } // 재생 수 정렬
        .sorted { genreRank[$0.value.0, default: -1] < genreRank[$1.value.0, default: -1] } // 장르 순위 정렬

	// 베스트앨범 추출
    var resultAlbum: [Int] = []
    var genrePicked1: Set<String> = []
    var genrePicked2: Set<String> = []
    
    for (key, value) in songSorted {
        let genre = value.0
        if !genrePicked1.contains(genre) { // 해당 장르에서 뽑는 1번째 곡
            resultAlbum.append(key)
            genrePicked1.insert(genre)
        } else if !genrePicked2.contains(genre) { // 해당 장르에서 뽑는 2번째 곡
            resultAlbum.append(key)
            genrePicked2.insert(genre)
        } else { continue } // 해당 장르에서는 더 이상 뽑지 않음
    }
    
    return resultAlbum
}

코드 평가

• 반환값을 추출하기 위해 songInfo가 꼭 필요한가? 필요하다면 왜 필요한가?
• 장르별 재생수 취합에서 장르 순위까지 딕셔너리 → 배열 → 딕셔너리로 구현되고 있다. 필요없는 과정을 줄일 수 없을까?
• for문에서 임시적으로 쓰이는 변수는 명시적으로 구분되게 할 수 없을까? (for문 안에서 처리하기 등)

개선한 코드 (Case B)

import Foundation

func solution(_ genres: [String], _ plays: [Int]) -> [Int] {
	// 곡 정보 (Key: 곡 고유번호, Value: (장르, 재생 수))
    var songInfo = Dictionary(uniqueKeysWithValues: zip(genres.indices, zip(genres, plays)))
    
    // 장르별 재생수 취합 (Key: 장르, Value: 재생수)
    var totalPlaysByGenre: [String: Int] = [:]
    for info in songInfo.values {
        let genre = info.0, plays = info.1
        totalPlaysByGenre[genre, default: 0] += plays
    }
    
    // 장르 순위
    let genreRank = totalPlaysByGenre.keys.sorted {
    	totalPlaysByGenre[$0]! > totalPlaysByGenre[$1]!
    }
    
    // 곡 순위
    let songSorted = songInfo
        .sorted { $0.key < $1.key } // 고유 번호 정렬
        .sorted { $0.value.1 > $1.value.1 } // 재생 수 정렬
        .sorted { genreRank.firstIndex(of: $0.value.0)! < genreRank.firstIndex(of: $1.value.0)! } // 장르 순위 정렬

	// 베스트앨범 추출
    var resultAlbum: [Int] = []
    var genrePicked: [String:Int] = [:]
    
    for (key, value) in songSorted {
        let genre = value.0
        if genrePicked[genre, default: 0] < 2 {
            resultAlbum.append(key)
            genrePicked[genre, default: 0] += 1 
        }
    }
    
    return resultAlbum
}

1. 반환값을 추출하기 위해 songInfo가 꼭 필요한가? 필요하다면 왜 필요한가?
   • 곡의 고유번호 기반 정보 접근: songInfo를 사용하면 고유번호를 기준으로 곡 정보를 쉽게 조회할 수 있다.
   • 정렬 및 결과 추출의 편의성: 각 곡의 정보를 한 번에 담고 있어 이후 정렬 및 베스트앨범 추출 과정에서 반복적인 데이터 조회를 피할 수 있다.
2. 장르별 재생수 취합에서 장르 순위까지 딕셔너리 → 배열 → 딕셔너리로 구현되고 있다. 필요없는 과정을 줄일 수 없을까?
   • 마지막의 딕셔너리를 만들지 않고, 대신 배열의 인덱스로 순서를 비교할 수 있다.
   • 하지만, 시간복잡도는 증가한다 (아래에 정리).
3. for문에서 임시적으로 쓰이는 변수는 명시적으로 구분되게 할 수 없을까? (for문 안에서 처리하기 등)
   • for문 안에 변수를 넣는 것은 구조적으로 어렵지만, for문 자체를 더 간략하게 줄일 순 있었다.

What I've learned:

Hash, 고차함수, 시간복잡도

Case A: 문제를 해결한 코드

.sorted { genreRank[$0.value.0, default: -1] < genreRank[$1.value.0, default: -1] }

시간복잡도 분석

• genreRank는 Dictionary이다.
• 딕셔너리에서 키를 기반으로 값(장르 순위)을 조회하는 시간복잡도는 O(1)이다.
• sorted 함수의 전체 시간복잡도는 O(n log n)이다.
  • 여기서 n은 songInfo의 곡 개수.
  • 정렬 과정에서 각 비교마다 딕셔너리 조회를 수행하지만, 조회 비용은 상수 시간 O(1)이므로 sorted 자체의 O(n log n)가 그대로 유지된다.

Case B: 개선한 코드

.sorted { genreRank.firstIndex(of: $0.value.0)! < genreRank.firstIndex(of: $1.value.0)! }

시간복잡도 분석

• genreRank는 배열이다.
• 배열에서 firstIndex(of:)를 호출하면 최악의 경우 배열의 모든 요소를 탐색해야 하므로 시간복잡도는 O(m)이다.
  • 여기서 m은 genreRank의 길이, 즉 고유한 장르의 수이다.
• sorted 함수의 전체 시간복잡도는 O(n log n) 호출당 비교 비용 O(m)이 추가되어 O(n m log n)이 된다.

위의 비교를 미루어 보아 Case A가 Case B보다 빠르다.
단, Case B에서는 Case A의 장르 순위 정렬 부분이 간략화되어 고차함수의 사용이 줄었다.
이를 고려해도 그런지 확인해보자.

장르 순위 정렬 비교

Case A

let genreByPlays = totalPlaysByGenre
    .sorted(by: { $0.value > $1.value }) // O(m log m)
    .map({ $0.key })                     // O(m)

• 정렬: 딕셔너리의 값을 기반으로 정렬하는 데 O(m log m).
• 매핑: 정렬된 결과에서 키만 추출하는 데 O(m).
• 이 부분의 총 시간복잡도는 O(m log m)이다.

Case B

let genreRank = totalPlaysByGenre.keys.sorted {
    totalPlaysByGenre[$0]! > totalPlaysByGenre[$1]! // O(1) 조회
} // O(m log m)

• 여기서는 딕셔너리 키를 정렬하면서 totalPlaysByGenre의 값을 비교한다.
• 이 정렬도 O(m log m)이다.
• 따라서 Case A와 Case B는 장르 순위 정렬 자체의 시간복잡도에서는 동일하다.

곡 순위 정렬 비교

Case A

.sorted { genreRank[$0.value.0, default: -1] < genreRank[$1.value.0, default: -1] }

• genreRank는 Dictionary.
• 딕셔너리 조회가 O(1)이므로, 정렬의 총 시간복잡도는 O(n log n).

Case B

.sorted { genreRank.firstIndex(of: $0.value.0)! < genreRank.firstIndex(of: $1.value.0)! }

• genreRank는 Array.
• firstIndex(of:)의 시간복잡도는 O(m) (최악의 경우).
• 따라서 sorted의 시간복잡도는 O(n m log n).

총 시간복잡도 비교

• Case A:

  • 장르 순위 정렬: O(m log m)
  • 곡 순위 정렬: O(n log n)
  • 총 시간복잡도: O(m log m + n log n)

• Case B:

  • 장르 순위 정렬: O(m log m)
  • 곡 순위 정렬: O(n m log n)
  • 총 시간복잡도: O(m log m + n m log n)

결론

• Case A는 곡 순위 정렬에서 더 효율적이므로, 곡 수(n)가 많아질수록 성능이 훨씬 더 좋다.
• Case B는 장르 순위 정렬에서 고차 함수가 줄어들어 코드가 간결하지만, firstIndex(of:)의 비효율로 인해 곡 순위 정렬에서 성능이 떨어진다.

따라서, 곡 수(n)가 많을 경우, Case A가 더 유리하다.

배열이 아닌 딕셔너리 자료구조를 이용한다는 것은, 곧 Hash를 이용한다는 것이기에 조회가 빠르다.
그런데 Hash값 또한 메모리에 저장되는 값이니 그 부분에서 손해를 보고 있을 것이다.
두 케이스의 공간복잡도를 한 번 비교해보자.

공간복잡도 비교

• (비교 과정 생략)
• Case A와 Case B는 동일한 공간복잡도를 가진다: O(n + m).
  • n: 곡의 수.
  • m: 고유한 장르의 수.

세부 차이

• Case A에서는 genreRank가 Dictionary로 저장되고, Case B에서는 Array로 저장된다.
  • Dictionary는 해시 기반이므로, 더 많은 추가 메모리를 사용할 수 있다(내부 해시 테이블).
  • 반면, Array는 선형 데이터 구조로서 상대적으로 메모리 효율이 좋다.

공간복잡도와 메모리 효율은 상관 관계가 있지만 같은 개념은 아닌가보다.
두 개념의 차이에 대해서 짚어보자.

공간복잡도와 메모리 효율

1. 공간복잡도

• 정의: 알고리즘이 실행되는 동안 사용하는 추가 메모리의 양을 입력 크기(n)에 따라 표현한 것.
• 측정 방식: 주로 빅오 표기법을 사용하여 입력 크기 증가에 따른 메모리 사용량의 성장률을 나타냄.
• 포커스:
  • 입력 데이터와 결과를 처리하기 위해 추가로 얼마나 많은 메모리를 사용하는지.
  • 알고리즘의 이론적인 메모리 사용 효율성.

예시

• 배열을 순회하면서 누적합을 계산할 때, 누적합을 저장하기 위한 변수만 필요하면 O(1) 공간복잡도를 가진다.
• 정렬 알고리즘에서 입력 크기 n에 비례하여 임시 배열을 생성하면 O(n) 공간복잡도를 가진다.

---

2. 메모리 효율

• 정의: 특정 데이터 구조나 알고리즘이 실제 메모리를 얼마나 효율적으로 사용하는지를 나타낸다.
• 측정 방식:
  • 구현 방식과 관련된 메모리 오버헤드(예: 포인터, 해시 테이블, 빈 공간 등).
  • 주로 실제 메모리 사용량과 관련된 최적화를 다룬다.

포커스

• 데이터 구조의 내부 설계가 얼마나 메모리를 효율적으로 사용하느냐.
• 같은 공간복잡도라도 구현 방식에 따라 메모리 효율성이 달라질 수 있음.

예시

• Array와 Dictionary 모두 공간복잡도가 O(n)이지만:
  • Array는 연속된 메모리 블록을 사용하여 메모리 오버헤드가 적다.
  • Dictionary는 해시 테이블 기반으로 설계되어 해싱을 위한 추가 메모리와 빈 슬롯 공간으로 인해 더 많은 메모리를 사용할 수 있다.

---

차이점 요약

공간복잡도	메모리 효율
이론적인 메모리 사용량 증가율	실제 메모리 사용량과 효율성
입력 크기 증가에 따른 메모리 변화율	데이터 구조 설계에 따른 메모리 낭비
빅오 표기법으로 표현	구현에 따라 상수 배수가 달라질 수 있음

---

결론

• 공간복잡도는 알고리즘의 이론적 메모리 요구량을 평가한다.
• 메모리 효율은 특정 데이터 구조나 구현의 실제 메모리 사용량을 최적화하는 것을 목표로 한다.

따라서 같은 공간복잡도를 가지더라도, 메모리 효율을 고려한 선택이 중요할 때가 많다.

Dictionary에 sorted() 메서드를 사용해서 문제를 풀었는데,
원래 Dictionary는 순서가 보장되지 않는 컬렉션이 아닌가?

Dictionary: Sequence

Swift의 Dictionary는 본래 순서가 없는 컬렉션이다. 키와 값의 쌍은 내부적으로 해시 테이블을 기반으로 저장되어 특정 순서를 보장하지 않는다. 그런데도 딕셔너리를 정렬된 형태로 다룰 수 있는 이유는 딕셔너리를 시퀀스로 변환하거나 정렬 메서드를 활용할 수 있기 때문이다.

1. Dictionary를 Array로 변환

Swift의 Dictionary는 기본적으로 순서를 보장하지 않지만, 딕셔너리의 키-값 쌍은 Array로 변환하여 시퀀스로 취급할 수 있다. Array는 순서가 있는 컬렉션이므로 정렬이 가능하다.

let dict = ["b": 2, "a": 1, "c": 3]

// 딕셔너리의 키-값 쌍을 배열로 변환한 후 정렬
let sortedByKey = dict.sorted { $0.key < $1.key }
let sortedByValue = dict.sorted { $0.value < $1.value }

print(sortedByKey)   // [("a", 1), ("b", 2), ("c", 3)]
print(sortedByValue) // [("a", 1), ("b", 2), ("c", 3)]

2. sorted(by:) 메서드

딕셔너리는 Sequence 프로토콜을 준수하기 때문에, sorted(by:) 메서드를 호출하면 정렬된 배열을 반환한다. 이 메서드는 정렬 기준을 클로저로 전달받아 사용자가 원하는 방식으로 키 또는 값을 기준으로 정렬할 수 있게 한다.

let sortedDict = dict.sorted { $0.key < $1.key }
// 반환 타입은 배열 [(Key, Value)]

3. 정렬된 결과는 새로운 배열

딕셔너리를 정렬할 때, 원래의 딕셔너리 자체는 변하지 않고 정렬된 결과는 새로운 배열로 반환된다. 따라서 딕셔너리 자체가 정렬된 상태로 유지되는 것이 아니라, 필요할 때마다 정렬된 배열을 생성하여 사용하는 방식이다.

---

요약

Swift의 Dictionary는 본래 순서가 없는 자료 구조지만, Array로 변환하거나 정렬 메서드를 사용하여 정렬된 결과를 배열 형태로 얻을 수 있다. 이는 Dictionary가 Sequence 프로토콜을 준수하기 때문이다.