58일차)알고리즘 문제(시소 짝꿍), 팀프로젝트-연락처 만들기

>알고리즘 문제

1.문제 

문제 설명

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

---

제한 사항

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

2. 솔루션

class Solution {
    fun solution(weight: IntArray): Long {
        var answer: Long = 0
        
        val weights=LongArray(1001)
        for(i in weight) weights[i]++
        
        
        for(i in 100..1000){
            answer+=Comb2(weights[i].toLong())
        }
        
        for(i in 100..999){
            if(weights[i]==0L) continue
            val p=hashSetOf(i*2,i*3,i*4)
            for(j in i+1..1000){
                if(i*4<j*2) break
                if(weights[j]==0L) continue
                val q=hashSetOf(j*2,j*3,j*4)
                if(p.intersect(q).isNotEmpty()) answer+=weights[i]*weights[j]
            }
        }
        
        
        return answer
    }
    
    fun Comb2(n:Long) = (n*(n-1))/2L
    
}

-동일 숫자를 가진 사람에 대해서는 모아둠

-동일 숫자를 가진 사람에 대해서 경우의 수는 n명이면 nC2

-서로 다른 무게를 가진 사람들이 시소짝꿍인 경우 경우의 수는 각각n,m명이면 nm

 

 

 

>팀프로젝트

https://appdevelopjava.tistory.com/79