프로그래머스 - 가장 큰 수(lv2)

 

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42746

문제 풀이

소스코드:

#include <functional>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename T>
class MaxHeap
{
private :
	vector<T> array;

	// c style
	//bool (*compare)(...);
	function<bool(T first, T second)> compare;

	static bool dcompare(T first, T second)
	{
		return first > second;
	}

public:
	MaxHeap()
	{
		compare = this->dcompare;
	}
	MaxHeap(function<bool(T first, T second)> usercompare)
	{
		compare = usercompare;
	}
	void insert(T x)
	{		
		array.push_back(x);
		int target = array.size();
		while( target > 1 && compare(x,array[(target/2)-1]) ) {
			array[target-1] = array[(target/2)-1];
			//cout << "target = " << target << ", target/2 = " << target/2 << endl;
			target /= 2;
			//cout << "target:" << target << endl;
		}
		//cout << "======end target========target:" << target << endl;
		array[target-1] = x;
	}

	T popMax()
	{
		//max is always first factor by heapify(insert)
		T max = array.front();

		//end factor moves to first factor
		array.front() = array.back();
		array.pop_back();

		//heapify
		T x = array.front();
		int parent=1, child=2;
		int arrSize = array.size();
		while(child <= arrSize) {
			if( !compare(array[child-1], array[child]) ) {
				child++;
			}
			if( compare(x,array[child-1]) || (x == array[child-1]) ) {
				break;
			}
			array[parent-1] = array[child-1];
			parent=child;
			child *= 2;
		}
		array[parent-1] = x;

		return max;
	}

	T getMax()
	{
		//max is always first factor by heapify(insert)
		return array.front();
	}


	bool isEmpty()
	{
		if(array.empty())
			return true;
		return false;
	}

	int factorSize()
	{
		return array.size();
	}

	void print()
	{
		cout << endl << "=============print=============" << endl;
		for (vector<int>::const_iterator item=array.begin(); item != array.end();++item) {
			cout<<*item << " ";
		}
		cout << endl << "===============================" << endl;
	}

	void printtree(int index, int space)
	{
		if(array.size() < index) {
			return;
		}

		space += 4;
		printtree((index*2)+1, space); //right
		for(int i=4;i<space;i++) {
			cout << " ";
		}

		cout << array[index-1] << endl;
		printtree((index*2), space); //left
	}

	void printtree()
	{
		printtree(1, 0);
	}
};


bool mycompare(string first, string second)
{
	return (first + second) > (second + first);
}

string solution(vector<int> numbers) {

	MaxHeap<string> myheap(mycompare);


	for(int i=0; i<numbers.size();i++) {
		myheap.insert(to_string(numbers[i]));
		//myheap.printtree();
	}
	

	if(myheap.getMax() == "0")
		return "0";

	string str;
	//vector<int> sortmax;
	while(!myheap.isEmpty()) {
		string max = myheap.popMax();
		//sortmax.push_back(max);
		str.append(max);
	}

	
/*
	//for log
	cout << "max sort : ";
	for (vector<int>::const_iterator i=sortmax.begin(); i != sortmax.end();++i) {
		cout<<*i << " ";
	}
	cout << endl;
*/
	return str;

}

/*

int main()
{
///////max sort
	vector<int> mynumbers{3,34,5,9};
	cout << solution(mynumbers) << endl;


	return 0;
}
*/

해설

기존에 만들어놓은 heap 정렬은 int형으로만 비교할 수 있는데, 이 문제를 풀다보니 int형으로는 비교할 수 없어 user 함수를 넣어 비교를 할 수 있게 변경했습니다.

user func에서 두 수를 string형으로 붙여서 비교한 후 heap 정렬에 넣습니다.

참고 : heap sort 이전 포스팅

https://juwith.blogspot.com/2020/11/algorithm-heap-sort.html

3과 34를 비교

최대값을 비교하며 heap 정렬