인프런 커뮤니티 질문&답변

코딩테스트합격하자님의 프로필 이미지
코딩테스트합격하자

작성한 질문수

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

74. 최소힙(STL priority_queue : 우선순위큐)

질문있습니다!

작성

·

159

0

#include<stdio.h>

#include<queue>

using namespace std;

int main(){

priority_queue<int> q;

int x;

while(true){

scanf("%d",&x);

if(x==-1) break;

if(x==0&&!q.empty()){

printf("this==%d\n",-q.top());

q.pop();

}

if(x==0&&q.empty()) printf("-1\n");

else q.push(-x);

}

return 0;

 

저가 작성한 코드를 실행시키면 3 5 2이 아닌 3 0 0이 나옵니다. * input(5 3 6 0 5 0 2 4 0 -1)

하지만 if(x==0&&q.empty()) printf("-1\n"); -> else if(x==0&&q.empty()) printf("-1\n");

로 수정하면 답이 정상적으로 나옵니다.

계속 고민해도 원인을 아직까지 찾지 못해서 도움을 청합니다.

 

}

답변 1

0

마지막 else q.push(x) 를 하셨는데, 본문대로 작성하시면 위에 if문를 실행하고도 다음 if을 또 실행 하게됩니다.

 

else if (x == 0 && q.empty()) printf("-1\n"); 를 하게되면 

위의 if (x == 0 && !q.empty()) 까지 묶여서 

if (x == 0 && !q.empty())

else if (x == 0 && q.empty()) printf("-1\n");

else q.push(x); 이 3개가 한세트지만

 

else if를 사용하지않으면

if (x == 0 && !q.empty()) 

이건 따로고

if (x == 0 && q.empty()) printf("-1\n");

else q.push(x);  만 세트입니다.

그래서 0을 입력하셨을때 위에서 if (x == 0 && !q.empty())를 실행하고 바로아래의

if (x == 0 && q.empty()) printf("-1\n"); 가 실행되고, 조건이 부합하지않으니 당연히 else인 q.push가 실행되어서

q에 0이 입력되기때문에 3 0 0이 출력됩니다.

그러나 else if를 추가하면 3개가 한세트가 되기때문에 맨위의 if (x == 0 && !q.empty()) 가 실행되면 자연스럽게

아래의 else if문과 else가 무시됩니다. 그래서 0이 입력되었을 때 else q.push(x)가 실행되지않으니,

q에 0이 들어가지 않습니다.

 

 

코딩테스트합격하자님의 프로필 이미지
코딩테스트합격하자

작성한 질문수

질문하기