백준 16936 나3곱2(c++)

https://www.acmicpc.net/problem/16936

16936번: 나3곱2

이 문제는 곱2, 나3이 섞인 수열이 존재하면, 순서에 맞는 수열을 찾는 문제입니다. 여기에서 핵심은 각 수를 소인수분해 했을 때, 3의 인수가 가장 많은 수가 제일 앞에 와야 합니다. 왜냐하면, 인수가 3이 많게 되면, 그다음 수도 자연스럽게 3으로 나누어 떨어지기 때문입니다. 그리고 3의 인수가 동일하다면 오름차순 정렬해주면 됩니다. (3의 인수가 동일한 경우에는 곱하기 2를 해줘야 하기에, 앞에 수가 뒤에 수의 절반이어야 합니다)

<코드>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
bool cmp(pair<int,long long> &p1, pair<int,long long> &p2) {
    if(p1.first == p2.first) {
        return p1.second < p2.second;
    }
    return p1.first > p2.first;
}

int main()
{
    int n;
    cin>>n;
    vector<pair<int, long long>> a(n); // 3의 개수, 실제 수
    for(int i=0;i<n;i++) {
        long long num;
        cin>>num;
        a[i].second = num;
        while(num % 3 ==  0) {
            num /= 3;
            a[i].first += 1;
        }
    }

    sort(a.begin(),a.end(),cmp);

    for(int i=0;i<n;i++) {
        cout<<a[i].second<<' ';
    }
}

우선적으로 3으로 나누어 떨어지면, 3의 개수를 증가시켜주고 나머지 수는 두 번째 요소에 둡니다. 그리고 비교함수 cmp를 통해, 첫 번째 요소를 기준으로 내림차순 정렬(3의 개수가 많은 수가 가장 먼저 와야 함), 만약 첫 번째 요소값이 같으면(3의 개수), 두 번째 요소를 기준으로 오름차순 정렬(3의 개수가 동일하다면 오름차순 정렬) 해주면 됩니다.