컴공 일기218
게시글 주소: https://orbi.kr/00061218409
C++ 표준 라이브러리 STL을 전혀 사용하지 않고, 최대 힙을 직접 구현한 풀이
#include <iostream>
#define HEAP_LEN 1000001
typedef int Heap;
using namespace std;
class CHeap
{
private:
int Num;
Heap heapArr[HEAP_LEN];
public:
CHeap() : Num(0) {}
int Empty()
{
if (Num == 0)
return 1;
else
return 0;
}
int GetParentIdx(int idx)
{
return idx / 2;
}
int GetLChildIdx(int idx)
{
return idx * 2;
}
int GetRChildIdx(int idx)
{
return GetLChildIdx(idx) + 1;
}
int GetHiPriChildIdx(int idx)
{
if (GetLChildIdx(idx) > Num)
return 0;
else if (GetLChildIdx(idx) == Num)
return GetLChildIdx(idx);
else
{
if (heapArr[GetLChildIdx(idx)] > heapArr[GetRChildIdx(idx)])
return GetLChildIdx(idx);
else
return GetRChildIdx(idx);
}
}
void push(int nParam)
{
int idx = Num + 1;
//큐의 index 0번은 비워놓는다. 부모/자식 index 계산의 편의를 위해서.
while (idx != 1)
{
if (nParam > heapArr[GetParentIdx(idx)])
{
heapArr[idx] = heapArr[GetParentIdx(idx)];
idx = GetParentIdx(idx);
}
else
break;
}
heapArr[idx] = nParam;
Num++;
}
int pop()
{
int retData = heapArr[1];
int LastData = heapArr[Num];
int parentIdx = 1;
int childIdx;
while (childIdx = GetHiPriChildIdx(parentIdx))
{
if (LastData >= heapArr[childIdx])
break;
heapArr[parentIdx] = heapArr[childIdx];
parentIdx = childIdx;
}
heapArr[parentIdx] = LastData;
Num--;
return retData;
}
void Print()
{
for (int i = 1; i <= Num; i++)
cout << heapArr[i] << endl;
}
bool empty()
{
if (Num == 0)
return true;
else
return false;
}
};
int main()
{
CHeap pq;
int N, x;
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> x;
if (x == 0)
{
if (pq.empty()) cout << 0 << '\n';
else
{
cout << pq.pop() << '\n';
}
}
else pq.push(x);
}
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
내일 입원함 4 2
응원해줘 나
-
독서실 가면 3 0
가끔 안씻고오는지 옆자리 냄새가 좀 남..
-
내프사가화질구지인이우 4 2
고화질사진은꾸츄가보인대서화질을낮춤
-
oh 엄마도 발광함 4 1
어떻게저런간사하고사악한웃음소리를낼수잇는거시디
-
하아ㅏㅏㅏㅏㅏㅏㅏㅏ 4 0
ㅏㅏㅏㅏㅏㅏㅏㅏㅏ
-
현역 순공시간 10 0
학교 가는날 기준으로 몇시간이 적당함 ㅜ 난 평균적으로는 4-5시간인데 ㅈ된듯
-
나는 얼굴이 5 1
억울하게 생겼다는 소리 많이 들음
-
6모대회 나갈걸 9 4
덕코가 너무 필요해 덕코줘
-
가끔보면 웃는게 일상인 사람과 5 1
우울한 표정이 일상인 사람이 있어
-
허수일기(33) 6 1
어째서 영어만 하면 졸린 것인가... . 다들 월요일 고생하셨어요!
-
누가 내게 다가온다면 난 이렇게 반짝일 수 있을까? (문학메타 10일차) 8 2
(…) 그렇게 원하든 원치 않든 사랑은 계속된다. 뜨거운 도시의 거리 위에서,...
-
감사합니다 4 2
막차로 상금 받음
-
오공완 ㅇㅈ 1 4
개폐급이라 말도 안 나옴
-
매일 좌절과 희망을 겪고, 영감과 지적 표류를 경험하는 일상. 흠냐뇨이!!!!
-
논술 어떻게 써야함 0 0
솔직히 수학도 못하고 글도 못써서 논술 하는 게 맞나 싶긴 한데 내신 4점따리라...
-
실모는 실전연습이니 평가원 기조따라가는게 맞지 않을까 6 3
근데 그러면 객관식 성의없다는 말들을듯
-
식단 확정함 10 1
8시에 삼각김밥이랑 닭가슴살 2시쯤에 간단하게 두유랑 닭가슴살 집에와서...
-
수잘<-대부분의 대학에서 반영비 크고 딴과목 답없어도 수리논술로 구제 ㄱㄴ
-
단어 알지? 1 0
싸워 오늘 고사장 나가서 싸워 바보같은 계산실수를해서 9번에서 틀린다거나 그거는...
-
담배 고양이 ㅈㄴ 귀여움 3 0
야니네코 야쿠네코 하메네코 아루네코 간사이네코 데부네코 조쿠네코 이모코 지카키네코...
-
시대인재 기숙 질문좀여 1 0
1. 어제 접수했는데 대기 오래걸릴까요?ㅜㅜ 2. 의대 특별서류전형이면 전장...
-
현돌 6평분석서 vs 실모 0 0
지금 메가캐쉬 4만원 있는데 뭐부터 푸는게 좋을까요? 6평 45점 7월 48점 맞았습니다
-
메좆의 파멸 3 2
기쁘디
-
월간조정식 0 0
지문은 좋은데 순삽같은거 정답 근거가 냄새 ㅈㄴ나네 우웩
-
개멋잇네 4 0
-
고마워 8 0
윤정아 수능때도 열어주라
-
영어 오답 1 0
다들 어케하심 ㅜㅜ ㅈㅂ알려줘
-
감사인사 메타를 열었군 3 0
이제 다른 메타로 넘어가고싶은데.
-
흑화한파마늘 12 5
-
운동 끝나고 집 옴 0 0
평소보다는 못 뛰었지만 오운완
-
6모대회상금감사인사 0 2
(상감인사)
-
9모내기할사람 22 1
조건)6모슈학88이하 존잘남
-
생윤 임팩트vs잘노는 기출 0 0
개념은 한바퀴 돌렸고 모고 2정도 나오는데 뭐 듣는게 좋을까요 패스는 둘다 있습니당
-
무물보 11 0
오징어다리맛잇네여 숙면은 글렀으니 노가리까기
-
제가 이걸로 꼭 복권의 하늘에 서겠습니다
-
국어 감 떨어졌을 때 0 0
한번도 이런 적 없고 국어는 모고 치면 백분위 97-99 사이였는데 문제 푸는거나...
-
쉬운데 내용 좋은 문항 9 1
은 의미가 없어 학생들은 안알아줘
-
수능급으로 머리에 정보가 안들어오는 상태를 최근 알아냄 0 2
새벽 5시에 공원 뛰면서 수특 독서 배경지식 지문 보기 진짜 ㄹㅈㄷ임 토할거같삼
-
수능수학전문과외 - 수능 때 6모보다 성적이 오르지 않으면 전액 환불해드립니다. 0 0
수능 때 6모보다 성적이 오르지 않으면 전액 환불해드립니다. 메가 대성 등 대형사...
-
에타 연합게시판에 똥글썼다가 15 3
실제로 본인 머리 좀 가려운김에 에타에 무샤워40시간 으흐흐 구릿 이따구로 똥글...
-
삼초고려 16 1
삼고초려
-
6모 대회 상금 인증 10 6
수능때도 좋은 결과 이뤄내봅시다.. 감사합니다 덕코
-
GPT 해킹 당함? 2 2
말 너무 못 알아 먹어서 자기 성찰과 석고대죄 시켰는데 죄송합니다아...!!...
-
맞팔 구함 4 0
ㅈㄱㄴ 잡담태그 잘달아요
-
7월 학력평가 Rainbowtable (국/수/영) 3 1
연도가 살짝 이상한 것 같긴한데 뭐 문제 없겠죠
-
아빠가 발광하는디 8 5
음이건소주두병이상은마셔야나오는텐션인데아니아빠베이비오늘왤케신남개귀엽넹
-
국어에서 ㅂㅅ짓을하지않는 가능세계 수학 28을 맞추는 가능세계
-
아니 지금까지 꾸준히 1등급 맞아왔는데 진학사 보니까 123개 대학이 국영수사과..?
-
오늘의 공부 9 1
국어 : 강기분 독서 033~035 (인강)수학수1 수능 기출의 미래 1등급...
-
6모대회 상금 감사합니다ㅎㅎ 5 3
잘 쓰겠습니다
C나 C++은 아닌데 typescript 로 tstl이라는 것을 구현한 국내 개발자가 계십니다. 타입스크립트쪽에서는 이미 글로벌에서 어느 정도 인지도가 있구요. 그 분의 결과물을 살펴보시면 지금 공부하시는 쪽이랑 좀 방향이 맞지 않을까 싶네요.
tstl이라면 그것도 일종의 라이브러리인가요...?
네 CPP의 STL을 Typescript로 구현한 라이브러리입니다.
물론 ts자체의 자료 구조로도 할려는 일을 다 할 수는 있지만, STL이 CPP에서 워낙 유명하다보니 STL에 포함된 자료구조를 Typescript로 구현한 분이 계십니다.
https://github.com/samchon/tstl
공부할 것들을 알려주셔서 너무 감사드립니다 ㅜㅜ 꼭 참고해보겠어요 :)