[프로그래머스] 시소 짝궁 Swift

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

 

입출력 예

weights	result
[100,180,360,100,270]	4

 

내가 푼 풀이

 

첫번째 접근방법(완전탐색) (시간초과)

- 두개의 포인터를 이용해 각 포인터의 원소가 시소짝궁인경우 세주는 방식을 사용

- 모두 같은 원소인 100인경우 각 포인터가 n씩 움직여야하므로 O(N^2)이 걸려서 시간초과가 걸림..

 

 

두번째 접근방법(자료구조를 이용)

- 한개의 원소로 다른 원소들을 하나씩 찾는방식이였다면 이제는 한개원소로 모든 원소를 비교해보는 방식을 사용

 

원소 a가 2m에 있다면 원소b가 a의 시소짝궁이 되려면

1. a * 2 = b * 2 ------> b = a * 2 / 2  -> b = a

2. a * 2 = b * 3 ------> b = a * 2 / 3

3. a * 2 = b * 4  -----> b = a * 2 / 4

가 성립해야한다.

 

원소 a가 3m에 있다면 원소 b가 a의 시소짝궁이 되려면

1. a * 3 = b * 3 -------> a = b

2. a * 3 = b * 4 -------> b = a * 3 / 4

가 성립해야한다.

 

원소 a가 4m에 있다면 

원소 b는 원소 a의 두배면서 2m에 있는경우

 

위의 경우의수를 종합하자면

원소 a의 시소짝궁은 아래와 같다.

1. 같은원소

2. a의 두배 (a: 4m, b: 2m)

3. a의 2/3배 (a: 2m, b: 3m)

4. a의 3/4배 (a: 3m, b: 4m)

 

시소의 갯수를 구하기위해 딕셔너리를 이용해서 각각 무게의 수를 저장한다.

저장한 딕셔너리를 이용해 위의 경우의수와 맞는 모든 수를 찾고 출력한다.

 

코드로 구현하면 다음과 같다.

 

import Foundation

func solution(_ weights:[Int]) -> Int64 {
    var answer = 0
    var dict = [Double: Int]()
    // 딕셔너리에 저장
    // Swift는 나눗셈을 하면 소숫점을 모두 버리므로 정확한계산을 위해 무게는 Double형식으로 입력
    for i in weights {
        if dict[Double(i)] == nil {
            dict[Double(i)] = 1
        } else {
            dict[Double(i)]! += 1
        }
    }
    
    // 시소짝궁 찾기
    // a: 4, b:3 이라면 a와 b를 조합할 수 있는 경우의수: a x b = 12
    for i in dict {
        // 같은 무게
        if i.value > 1 {
            answer += (i.value * (i.value - 1)) / 2
        }
        // 2배의 무게
        if dict[i.key * 2] != nil {
            answer += (i.value * dict[i.key * 2]!)
        }
        // 2/3배의 무게
        if dict[i.key * 2 / 3] != nil {
            answer += (i.value * dict[i.key * 2 / 3]!)
        }
        // 3/4배의 무게
        if dict[i.key * 3 / 4] != nil {
            answer += (i.value * dict[i.key * 3 / 4]!)
        }
        
    }
    return Int64(answer)
}