<프로그래머스> 시소 짝꿍(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EC%8B%9C%EC%86%8C%20%EC%A7%9D%EA%BF%8D

[프로그래머스]

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

 

아주 오래 걸렸다...

어제부터 시작했는데 어제 시간 안에 못 끝내서 오늘까지 이어지고 많은 실패 끝에 통과한 문제

문제는 아주 간단하고 쉬운 줄 알았는데 크기가 커지니까 쉽지 않더라

 

가장 처음에는 완전탐색으로 갔다.

그랬다가 바로 메모리초과를 맞아버렸다.

조합을 만드는 과정에서 이러한 문제가 발생한 것으로 보인다.

조합, 최대공약수를 이용한 풀이로 가장 이해하기 쉬웠지만 크기가 큰 문제에서는 해결책이 되지 못했다.

 

이렇게 풀고 시간이 없어 오늘로 넘어왔다.

 

O(N^2)은 안 된다는걸 알게 되어서 O(N) 안에 끝내기 위해 머리를 쓰기 시작했다.

그 첫 방법은 무게로 나올 수 있는 모든 크기를 담는 배열을 만드는 것이었다.

그리고 해당 무게가 나올 때 배열에 넣고 배열 원소의 크기가 1보다 커지면 같은  비율이라는 거니까 answer의 값을 1 올렸다.

같은 값일 때는 2를 빼서 한개만 올라가도록 했다.

아주 완벽하다고 생각하고 냈는데 실패였다.

 

고민을 하고 힌트를 찾아다녔는데 map을 쓰는 케이스가 좀 있는 거 같았다.

그래서 groupingBy를 이용해 Map을 구성했다.

그리고 Map의 키와 값을 이용해, 나올 수 있는 비율을 고려해 문제를 풀었다.

하지만 결과는 실패였다.

 

이제 머리가 너무 멍해지기 시작했다.

다음으로 해본것은 형변환이었다.

answer가 Long이었기에 answer에 값을 넣는 부분들을 모두 Long타입으로 변환해주었다.

그리고 제출했더니 전보다는 덜 틀렸다.

하지만 이제 뭐가 남았는지 도저히 알 수가 없었다.

 

그러다 마지막으로 한 것은 형변환시 생기는 오차처리였다...

생각보다 간단한 문제였다.

물론 코드가 조금 지저분해졌지만 잘 해결이 되었다.

다른 사람들의 코드를 봐도 비슷한 흐름들이 많더라

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    private var answer: Long = 0
    fun solution(weights: IntArray): Long {
        var weightsGroup = weights.toList().groupingBy { it }.eachCount()

        for (weight in weightsGroup) {
            if (weight.value >= 2) {
                answer += weight.value.toLong() * (weight.value.toLong() - 1) / 2
            }

            checkWeight(weightsGroup, weight.key, 2.0 / 3.0)
            checkWeight(weightsGroup, weight.key, 2.0 / 4.0)
            checkWeight(weightsGroup, weight.key, 3.0 / 4.0)
        }

        return answer
    }

    private fun checkWeight(w: Map<Int, Int>, key: Int, ratio: Double) {
        if ((key * ratio) - (key * ratio).toInt() == 0.0 && w.containsKey((key * ratio).toInt())) answer += (w[(key * ratio).toInt()]!!.toLong() * w[key]!!.toLong())
    }
}