[Programmers] 시소 짝궁

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/152996

프로그래머스

계산하는 과정에서 오버플로우가 발생하기 쉬운 문제였습니다.
또한, weights의 길이가 최대 10만이기 때문에 시간복잡도 O(N) 혹은 O(NlogN) 안에 풀어야 하는 문제였습니다.

저는 O(N) 방식으로 풀었으며 알고리즘은 아래와 같습니다.
1. 우선 맵을 선언하고 weights를 순회하면서 각 무게의 등장 횟수를 기록했습니다.
2. 등장한 모든 무게에 대해서 아래와 같은 연산을 진행합니다.
2.1 우선, 동일한 위치에 있을 때 짝꿍을 구해주는데 자기 자신과는 짝이 될 수 없으므로 아래와 같이 계산해 줍니다.
2.2 [ X = 해당 무게의 등장 횟수 ]라고 정의한 뒤 answer에 (X * (X - 1)) / 2를 더해줍니다.
주의: X * (X - 1)을 계산할 때 int 범위를 벗어날 수 있습니다.
2.3 입출력 예시를 보면 서로 다른 몸무게에 대해서 [4m, 2m] 거리, [3m, 2m] 거리, 그리고 [4m, 3m] 거리에 마주 보고 앉을 경우 균형이 이루어지는 케이스가 소개됩니다. 따라서, 각 몸무게에 대해 해당 비율을 곱한 몸무게의 등장 횟수 Y를 구해줍니다. X와 Y는 짝꿍이고 동일 인물일 수 없으므로 answer에 X * Y를 더해줍니다.
3. 2번을 통해 구해준 answer를 반환해 줍니다.

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~