[프로그래머스] 시소 짝꿍 - C++

---

N이 10만이다 O(N^2)으로 풀 수 없다. 따라서 정렬을 한 다음 풀거나 바로 linear 하게 풀어야 한다.

우선, 해당 weight 의 사람이 얼마인지 센다.

짝꿍의 경우의 수는 무게의 비율이

1 : 1 / 2 : 1 / 2 : 3 / 3 : 4 총 4가지 경우가 있다.

i번째 사람의 몸무게를 생각할때

1. 무게가 같은 사람은 nC2 만큼의 짝꿍이 나온다. 이는 무게가 같은 사람을 확인할 때 1번만 진행하여야 한다.

2. 무게가 다르면 해당 비율의 무게의 사람 수만큼 짝꿍이 될 수 있다.

 

---

linear 하게 풀어야겠다는 생각을 빨리 했지만 방법을 찾는 데는 조금 걸렸다. 중복처리를 잘해야 한다!