백준 11279 최대 힙 c++

0이 입력되면

최대 값 혹은 0 출력,

그 외의 값이 입력되면 배열에 저장

 

 

 

 

 

처음 생각했던 코드

deque로

최댓값 한개를 맨앞에 두고

0이 입력됐을때

pop하고 최댓값을 또 맨앞에 두는 방식

정렬되지 않은 리스트에서

최댓값을 찾기 위해

0이입력될때마다 완전탐색을 했다

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int findidx(deque<int> dq);

bool cmp(int a, int b){
    return a>b;
}

int main(){

    deque<int> dq;
    int n;
    cin>>n;
    int max=0;

    for(int i=0; i<n; i++){
        int temp;
        cin>>temp;
        if(dq.size()>0){
            max=dq[0];
        }

        if(temp==0){
            if(dq.size()==0){
                cout<<0<<"\n";
            }

            else{
                cout<<dq[0]<<"\n";
                dq.pop_front();
                int maxidx=findidx(dq);
                dq.push_front(dq[maxidx]);
                dq.erase(dq.begin()+maxidx+1);
                
            }


        }
        else{
            if(dq.size()>0){
            if(max<temp){
                dq.push_front(temp);
            }
            else{
            dq.push_back(temp);
            }
            }

            else{
                dq.push_back(temp);
            }
        }
    }


    return 0;
}

int findidx(deque<int> dq){
    int max=0;
    int maxidx=0;
    for(int i=0; i<dq.size(); i++){
        if(max<dq[i]){
            maxidx=i;
            max=dq[i];
        }
    }
    return  maxidx;
}

 

시간초과가 났다

최대값만 찾기 위해

나머지 값들을 무작위로 삽입해서 그런 것 같았다

 

 

 

 

 

 

그래서 생각한코드

삽입할때 부터

내림차순으로 삽입하자

삽입할때 값이 들어가야할 곳을 찾아서

삽입해주는 형식으로 했다

내 생각에 이거 잘 짠거같은데

또 시간초과가 났다

 

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int findidx(deque<int> dq,int);



int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 

    deque<int> dq;
    int n;
    cin>>n;
    int max=0;

    for(int i=0; i<n; i++){
        int temp;
        cin>>temp;
        if(temp==0){
            if(dq.size()==0){
                cout<<0<<"\n";
            }
            else{
                cout<<dq[0]<<"\n";
                dq.pop_front();
            }

        }
        else{
            if(dq.size()==0){
                dq.push_front(temp);
            }
            else{
                int idx=findidx(dq,temp);
                dq.insert(dq.begin()+idx,temp);
            }
        }
        

    }


    return 0;
}

int findidx(deque<int> dq,int temp){
    int idx=-9999;
    for(int i=0; i<dq.size(); i++){
        if(dq[i]<temp){
            idx=i;
            break;
        }
    }
    if(idx==-9999){
        return dq.size();
    }
    else{
        return idx;
    }
}

 

 

 

 

 

 

이거 보다 더 시간복잡도를 줄일 생각이 안나서

정답을 찾아봤다

#include <iostream>
#include <queue>

using namespace std;
int main(void)
{

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
	priority_queue<int> myp_q;

	int n;
	int num;

	cin >> n;

	int i;
	for (i = 0; i < n; i++)
	{
		cin >> num;
		if (num == 0)
		{
			if (myp_q.empty() == true)
			{
				cout << "0" << "\n";
			}
			else
			{
				cout << myp_q.top() << "\n";
				myp_q.pop();
			}
		}
		else
		{
			myp_q.push(num);
		}
	}
	return 0;
}

priority queue로 선언해서

그냥 삽입하면 내림차순으로 삽입되나보다

근데 이것도 따지고보면

삽입할때 내림차순으로 삽입해야하니까

내가 짠 알고리즘과 방식은 동일하다

그러나 나는 뭔가 못짰나 보다

라이브러리가 제일 좋은듯하다

priority queue를 통해 내림차순, 오름차순 삽입이 가능하고

최대 힙 구현이 가능하다는 것을 알게되었다