N이 10만이다 O(N^2)으로 풀 수 없다. 따라서 정렬을 한 다음 풀거나 바로 linear 하게 풀어야 한다.
우선, 해당 weight 의 사람이 얼마인지 센다.
짝꿍의 경우의 수는 무게의 비율이
1 : 1 / 2 : 1 / 2 : 3 / 3 : 4 총 4가지 경우가 있다.
i번째 사람의 몸무게를 생각할때
1. 무게가 같은 사람은 nC2 만큼의 짝꿍이 나온다. 이는 무게가 같은 사람을 확인할 때 1번만 진행하여야 한다.
2. 무게가 다르면 해당 비율의 무게의 사람 수만큼 짝꿍이 될 수 있다.
linear 하게 풀어야겠다는 생각을 빨리 했지만 방법을 찾는 데는 조금 걸렸다. 중복처리를 잘해야 한다!
'코딩 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 리코쳇 로봇 - C++ (0) | 2023.03.19 |
|---|---|
| [프로그래머스] 택배 배달과 수거하기 (0) | 2023.03.16 |
| [프로그래머스] 숫자 변환하기 - C++ (0) | 2023.03.09 |
| [프로그래머스] 인사고과 - C++ (0) | 2023.03.08 |
| [프로그래머스] 연속 펄스 부분 수열의 합 - C++ (0) | 2023.03.06 |