문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

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

문제 풀이

소스코드:

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


using namespace std;

template <typename T>
class MaxHeap
{
	vector<pair<int, T>> array;

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

	pair<int, T> popMax()
	{
		//max is always first factor by heapify(insert)
		pair<int, T> maxpair(array.front().first,array.front().second);

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

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

		return maxpair;
	}

	pair<int, 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;
		typename vector<pair<int, T> >::iterator iter;
		for(iter = array.begin(); iter != array.end(); iter++){
			cout<<iter->first << "(" << iter->second << ")" << " ";
		}
		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].first << "(" << array[index-1].second << ")"<< endl;
		printtree((index*2), space); //left
	}

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

};

template <typename T>
class MinHeap
{
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:
	MinHeap()
	{
		compare = this->dcompare;
	}
	MinHeap(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 popMin()
	{
		//min is always first factor by heapify(insert)
		T min = 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 min;
	}

	T getMin()
	{
		//min 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);
	}
};



vector<int> solution(vector<int> answers) {
    vector<int> answer;

	vector<vector<int>> person{
		{1,2,3,4,5},
		{2,1,2,3,2,4,2,5},
		{3,3,1,1,2,2,4,4,5,5},
	};

	int sum[3]={0,};
	MaxHeap<int> maxheap;

	for(int i=0; i<person.size(); i++) {
		for(int j=0; j<answers.size(); j++) {
			//cout << person[i][j%person[i].size()] << endl;
			int num = j%person[i].size();
			if(person[i][num] == answers[j])
				sum[i]++;
		}
		//cout << "sum ! " << sum[i] << endl;
		maxheap.insert(sum[i],i+1);
	}

	//maxheap.printtree();
	while(!maxheap.isEmpty()) {
		pair<int,int> maxpair = maxheap.popMax();
		answer.push_back(maxpair.second);
		pair<int,int> next = maxheap.getMax();
		if(maxpair.first != next.first){
			break;
		}
	}

	//sort
	MinHeap<int> rank;
	while(answer.size() > 0) {
		rank.insert(answer.back());
		answer.pop_back();
	}

	//rank.printtree();
	while(!rank.isEmpty()) {
		int min = rank.popMin();
		answer.push_back(min);
	}


	return answer;
}

/*
int main()
{
	vector<int> myanswers{
		1,3,2,4,2
	};


	vector<int> ret = solution(myanswers);
	cout << "ret {";
	for(typename vector<int>::iterator itr = ret.begin(); itr != ret.end();++itr)
	{
		cout << *itr << ", ";
	}
	cout << "}" << endl;

	cout << endl;
}
*/

해설

단순 3명의 비교이지만 범용성을 위해 person이라는 2차원 vector를 만들었습니다.

	vector<vector<int>> person{
		{1,2,3,4,5},
		{2,1,2,3,2,4,2,5},
		{3,3,1,1,2,2,4,4,5,5},
	};

각 person별로 문제의 갯수만큼 나의 답안 list를 비교합니다.

그리고 정답 갯수는 최대순서대로 max heap으로 sorting합니다.

이 때 정답 갯수와 어떤 사람인지에 대한 정보가 같이 가야하기 때문에 2차원 heap으로 sorting합니다.

	for(int i=0; i<person.size(); i++) {
		for(int j=0; j<answers.size(); j++) {
			//cout << person[i][j%person[i].size()] << endl;
			int num = j%person[i].size();
			if(person[i][num] == answers[j])
				sum[i]++;
		}
		//cout << "sum ! " << sum[i] << endl;
		maxheap.insert(sum[i],i+1);
	}

* heap에 대한 이전 포스팅 참고 :

https://www.blogger.com/blog/post/edit/4731923268701669730/4328302319687934456?hl=ko

* 2차원 heap 참고 : https://github.com/juwith/jsutilspp/blob/master/sort-heap-2d/src/heapsort2d.cpp

이렇게 정렬된 정답의 갯수를 다시 사람 순으로 정렬합니다.

	//sort
	MinHeap<int> rank;
	while(answer.size() > 0) {
		rank.insert(answer.back());
		answer.pop_back();
	}

	//rank.printtree();
	while(!rank.isEmpty()) {
		int min = rank.popMin();
		answer.push_back(min);
	}

이 블로그 검색

jusang blog

프로그래머스 - 모의고사(lv1)

문제 설명

문제 풀이

해설

결과

댓글

댓글 쓰기