[프로그래머스/Swift] 152996번 - 시소 짝꿍

🔗 문제 링크

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

💡 구현 아이디어

1. 중복된 무게의 개수 정리
2. 2,3,4배를 한 무게를 정리
3. 같은 무게에 대한 순서쌍 개수를 구함
4. 최초의 무게가 같으면 2, 3, 4배에서 중복으로 순서쌍을 구해지므로 3, 4배의 순서쌍 개수를 제거
5. 결과 반환

💻 코드

import Foundation

func solution(_ weights:[Int]) -> Int64 {
  var weightMap: [Int : [Int]] = [:] // key: 무게, value: 해당 무게를 만들 수 있는 weight(idx)
  var dupleMap: [Int : Int] = [:] // key weights에 담긴 무게, value: 중복 개수
  // 중복 개수
  weights.forEach { dupleMap[$0, default: 0] += 1 }
  // 무게(2,3,4배)에 따른 개수
  weights.enumerated().forEach {
    weightMap[$0.element * 2, default: []].append($0.offset)
    weightMap[$0.element * 3, default: []].append($0.offset)
    weightMap[$0.element * 4, default: []].append($0.offset)
  }
  // 짝꿍의 수
  let result = weightMap.reduce(0) { $0 + $1.value.count * ($1.value.count-1) / 2 }
  // 중복 계산된 짝궁의 수
  let t: Int = dupleMap.reduce(0) { $0 + $1.value * ($1.value - 1) }
  return Int64(result-t)
}

❌ 틀린 이유 및 틀린 부분

• O(n^2)으로는 당연히 안된다 생각해서 이런저런 방법으로 바꿔서 했지만 결국 O(n^2)에 가까운 알고리즘만 짜져서 시간초과가 나왔다..
• 고민해서 전체 순서쌍 개수 - 중복 계산된 순서쌍 개수 라는 생각이 나왔고 다시 제출해서 정답

⏳ 시간 복잡도

O(n) - 전체 개수 * 3의 개수를 순회

📌 풀이 또는 기억할 정보