백준16936 - 나3곱2

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

16936번: 나3곱2

2와 3을 인수로 몇 개나 갖는지 조사한 후 기준에 맞게 정렬한다. 정렬 기준 첫번째는 3을 인수로 많이 가지는 순이고 두번째 기준은 2를 인수로 적게 가지는 순이다.

 

ex.) 8 72 16 36 24 32

***2와 3을 인수로 몇개 가지는지 표현***

8 : 2^3

72 : 2^3 * 3^2

16 : 2^4

36 : 2^2 * 3^2

24 : 2^3 * 3^1

32 : 2^5

 

***정렬한 결과

36 : 2^2 * 3^2

72 : 2^3 * 3^2

24 : 2^3 * 3^1

8 : 2^3

16 : 2^4

32 : 2^5

 

***수열***

36 72 24 8 16 32

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//1번째 비교 대상은 인수로 3이 많은 수, 2번째 비교 대상은 인수로 2가 적은 수
bool compare(pair<long long int, pair<int,long long int>> a, pair<int, pair<int,long long int>> b) {
	if (a.first == b.first) { //인자로 3의 수가 같은 경우
		return a.second.first < b.second.first; //인자로 2의 수를 비교
	}
	return a.first > b.first;
}

int main() {
	int n;
	vector < pair<long long int, pair<long long int, long long int>>> v; //첫번째는 3의 인자수, 두번째는 2의 인자수, 세번째는 수열의 원소

	cin >> n;
	for (int i = 0; i < n; i++) {
		long long int num; //수열의 원소
		long long int check2; //2를 인수로 가지는 경우 총 몇 개의 2가 들어갔는지 확인하기 위해 임시로 담아놓는 변수
		long long int check3; //3을 인수로 가지는 경우 총 몇 개의 3이 들어갔는지 확인하기 위해 임시로 담아놓는 변수
		long long int cnt2 = 0; //2를 인자로 몇 개나 가지는지
		long long int cnt3 = 0; //3을 인자로 몇 개나 가지는지

		cin >> num;
		
		//2와 3을 인수로 몇 개나 가지는 원소를 임시로 담아놓는다.
		check2 = num;
		check3 = num;

		//2를 인수로 몇 개나 갖는지 찾는다.
		while (1) {
			if (check2 % 2 != 0) {
				break;
			}
			check2 = check2 / 2;
			cnt2++;
		}
		
		//3을 인수로 몇 개나 갖는지 찾는다.
		while (1) {
			if (check3 % 3 != 0) {
				break;
			}
			check3 = check3 / 3;
			cnt3++;
		}

		v.push_back(pair<long long int, pair<long long int, long long int>>(cnt3, pair<long long int, long long int>(cnt2, num))); //3의 인수 갯수, 2의 인수 갯수, 수열의 원소를 넣는다.
	}

	sort(v.begin(), v.end(), compare); //sort로 정렬, 기준은 compare함수

	//벡터의 각 원소 세 번째 요소가 수열의 원소
	for (int i = 0; i < v.size(); i++) {
		cout << v[i].second.second << ' ';
	}
}