시소 짝궁 - Kotlin

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

프로그래머스

문제 설명

 

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

 

나의 풀이 - 1차

 이 문제를 봤을 때 나는 바로 브루트포스를 이용해서 문제를 해결하려고 하였다. 다만 weights의 길이가 최대 100,000 임으로 O(N²)의 시간 복잡도를 가진 브루트 포스를 사용한다는 것이 불안하기는 했다. 실제로 실행을 해보니 테스트 케이스 9, 10, 11, 13, 14, 15에서 시간 초과가 나오고 말았다.

class Solution {
    fun solution(weights: IntArray): Long {
        var answer: Long = 0
        
        for (i in weights.indices) {
            for (j in i + 1 until weights.size) {
                if (findSeesawPair(i, j, weights))  answer++
            }
        }
        
        return answer
    }

    fun findSeesawPair(a: Int, b: Int, weights: IntArray): Boolean {
        for (i in 2..4) {
            for (j in 2..4) {
                if (i * weights[a] == j * weights[b])
                    return true
            }
        }
        return false
    }
}

 

나의 풀이 - 2차

 브루트 포스를 그대로 이용하지만 정렬을 사용해서 첫번째 반복문에서 선택한 값이 두번째 반복문에서 선택한 값보다 무조건 작게 만들었다. 이렇게 되면 시소의 균형을 맞출 수 있는 조건은 4가지가 된다. 

class Solution {
    fun solution(weights: IntArray): Long {
        var answer: Long = 0
        val weight = weights.sorted().toIntArray()
        
        for (i in weight.indices) {
            for (j in i + 1 until weight.size) {
                if (weight[i] == weight[j]) {
                    answer++
                    continue
                }
                if (weight[i] * 2 == weight[j]) {
                    answer++
                    continue
                }
                if (weight[i] * 3 == weight[j] * 2) {
                    answer++
                    continue
                }
                if (weight[i] * 4 == weight[j] * 3) {
                    answer++
                    continue
                }
            }
        }
        return answer
    }
}