[프로그래머스/Swift] 147354번 - 테이블 해시 함수

🔗 문제 링크

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

💡 구현 아이디어

1. 기준에 맞춰 정렬
2. S_i를 구함
3. 2진수로 변경
4. 2진수로 변경된 값으로 XOR을 구함

💻 코드

import Foundation

func solution(_ data:[[Int]], _ col:Int, _ row_begin:Int, _ row_end:Int) -> Int {
    
    var arr: [[String]] = []
    
    // 입려된 데이터 정렬
    var data = data.sorted(by: {
        if $0[col-1] == $1[col-1] {
            return $0[0] > $1[0]
        }
        return $0[col-1] < $1[col-1]
    })
    
    for i in (row_begin-1)..<row_end {
        var S: Int = 0
        for num in data[i] {
            S += num % (i+1)
        }
        let temp = String(S, radix: 2).reversed().map{ String($0) }
        arr.append(temp)
    }
    
    var result = arr[0]
    for i in 1..<arr.count {
        result = calculateXOR(A: result, B: arr[i])
    }
    
    return Int(result.reversed().reduce("", +), radix: 2)!
}

func calculateXOR(A: [String], B: [String]) -> [String] {
    var result: [String] = []
    var aIdx: Int = 0
    var bIdx: Int = 0
    while aIdx < A.count && bIdx < B.count {
        if A[aIdx] == B[bIdx] {
            result.append("0")
        } else {
            result.append("1")
        }
        aIdx += 1
        bIdx += 1
    }
    result += A[aIdx..<A.count]
    result += B[bIdx..<B.count]
    return result
}

❌ 틀린 이유 및 틀린 부분

XOR을 전체를 한번에 계산하려고 해서 틀렸다.

XOR을 구할때는 한번에 한쌍씩 계산하자

⏳ 시간 복잡도

계산자체는 O(N)으로 구해지는거 같은데 중간에 정렬이 있어서 O(N^2)이나 O(N logN)으로 잡힌다

📌 풀이 또는 기억할 정보

꼭 2진수로 변경후 XOR을 진행하지 않아도 됐다!

var result = 0
for i in row_begin...row_end {
	result ^= sortedData[i-1].reduce(0) { $0 + $1%i }
}