프로그래머스 더 맵게 문제 풀이

안녕하세요! 오늘은  프로그래머스 문제  더맵게 를 풀었습니다.

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

문제 자체는  heap에 대한 이해만 있다면 충분히 쉽게 풀 수 있는 문제인데요, 

전 힙 stl이 익숙하지 않아서 직접 구현했습니다.

 

1. 우선  스코빌 지수가 가장 작은값이 루트로 와야하므로,   최소힙을 구성했습니다.

2. 최소힙을 만들고,   맨위 원소 2개를 뽑아  계산후,  다시  힙에 삽입.  

이 두과정을 반복했습니다.

#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

//우선 최소힙읆 만들어라

//일단 단순 일차원배열
struct heap{
	int elements[1000001];
	int size;
	
	heap(){		
		size = 0;
	}
	void swap(int *a, int *b){
		int temp = *a;
		*a = *b;
		*b = temp;	
	}
	
	bool insert(int data){
		
		int temp = size+1;
		if(temp > 1000000) return false;

		while(temp != 1 && elements[temp/2] > data){
			elements[temp] = elements[temp/2];
			temp = temp / 2;
		}
		
		elements[temp] = data;
		size++;

		return true;
	}
	
	void print(){
		for(int i=1;i<=size;i++){
			printf("%d ",elements[i]);
		}
		printf("\n");
	}
	
	bool pop(int *pOutData){
		if(size == 0) return false;
		
		*pOutData = elements[1];
		
		//힙 재구성 
		elements[1] = elements[size--];
		
		int parent = 1;
		int pos = 2;
		
		//반복하기  
		while(pos<=size){ 
		
			if(pos+1<=size &&  elements[pos] > elements[pos+1]){
				pos = pos+1;
			}
			
			if(elements[parent] > elements[pos]){
				swap(&elements[parent], &elements[pos]);
				parent = pos;
				pos = pos*2;
			}
			else{
				//부모가 아래 자식보다 작으니 패스 
				break;	
			}
		}
		
		return true; 
	}
};


heap h;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    for(int i=0;i<scoville.size();i++){
    	h.insert(scoville[i]);
    }
    
    int pOutData;
	 
    while(h.pop(&pOutData) && pOutData < K){
    	answer++;
    	//하나 더꺼내.
		int pOutData1;
		
		if(h.pop(&pOutData1)){
			h.insert(pOutData + pOutData1*2);
		}
	}
	
	if(pOutData < K){
		answer = -1;	
	}
	
    return answer;
}


int main()
{
	int n;
	scanf("%d",&n);
	
	vector<int> scovi;
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		scovi.push_back(t);
	}
	
	int k; 
	scanf("%d",&k);
	
	printf("%d",solution(scovi,k));
	
}

 

 

물론  애초에  주어진 벡터를 갖고  힙으로 바로 바꿀수도있지만,   원소 두개 뽑아 섞고 다시 넣는과정에서 비효율적입니다. (넣은 원소에 대해서만 따로 올바른 위치 찾아주면 상관없지만 )

그래서  매번 추가 삽입 삭제를 하는데 좀더 나은,  비어있는 힙을 만들고  처리하는 식으로  구현하게 됐네요 ㅎㅎ

 

주어진 벡터를 바로 힙으로 바꾸는 버전 코드.

#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

//우선 최소힙읆 만들어라

//일단 단순 일차원배열
struct heap{
	void makeHeap(vector<int> &vec, int size, int parent){
		
		if(parent*2>size ||parent<1) return;
		
		int i = parent*2;
		
		//작은놈 위로 올리기 위해  더작은값 위치찾음 
		if(i+1<=size && vec[i] > vec[i+1]){
			i=i+1;
		}
		
		//자식이 더 작다면 부모랑 위치교체  
		if(vec[parent] > vec[i]){
			int t = vec[parent];
			vec[parent] = vec[i];
			vec[i] = t;
			
			//위치교체후    교체된애 자식트리  힙구조 다시 만들기
			makeHeap(vec, size, i);
		}
		
		//남은 애들도 변경 
		makeHeap(vec, size, parent-1);
	}
	
	bool pop(int *pOutData, vector<int> &datas, int size){
		//해당 애 꺼내고 다시 힙정렬
		if(size<1) return false;
		
		*pOutData = datas[1];
		datas.erase(datas.begin()+1);
		makeHeap(datas, size-1, (size-1)/2);  
		return true;
	}
	
	void print(vector<int> datas){
		for(int i=1;i<datas.size();i++){
		printf("%d ",datas[i]);
		}
		printf("\n");
	}
};

heap h;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    scoville.insert(scoville.begin(),0);
	
    h.makeHeap(scoville, scoville.size()-1, (scoville.size()-1)/2);
   // h.print(scoville);
    int pOutData=0;
    while(h.pop(&pOutData, scoville, scoville.size()-1) && pOutData < K){
    	answer++;
    	//하나 더꺼내.
		int pOutData1;
		
		if(h.pop(&pOutData1, scoville, scoville.size()-1)){
			scoville.push_back(pOutData + pOutData1*2);
			h.makeHeap(scoville, scoville.size()-1, (scoville.size()-1)/2);
		}
	}
	
	if(pOutData < K){
		answer = -1;	
	}
	
    return answer;
}


int main()
{
	int n;
	scanf("%d",&n);
	
	vector<int> scovi;
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		scovi.push_back(t);
	}
	
	int k; 
	scanf("%d",&k);
	
	printf("%d",solution(scovi,k));
	
}

 

 

 

hackee.tistory.com/168

[C. C++] 과외 해드립니다!

hackee.tistory.com/255

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

 

 

초등, 중등, 고등  1:1 원격 c언어 교육문의

010 - 4537 - 7998

 

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반  문의주세요!