컴공 일기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를 선물하세요.
-
2022 현역때 통합 첫 수능 봤던 03틀딱인데.. 군대 갔다오고 27수능을...
-
수시 결정 고민중 5 1
경희한 인문 가천한 수리 이거 두개는 확정 나머진 고민중 인문은 걍 쓸게 없고...
-
7모 수학 0 0
미적분 28번 틀 96이면 백분위랑 표점 몇임요?
-
여름방학 올오카 0 0
5,6등급 노베이스입니다. 여름방학 3주 안에 올오카 독서,문학 전부 다 하기엔...
-
실모의 모순 1 2
수학기준 80-88: 기분 안좋음. 운영 개박고 킬러도 못건드림. 오답하기도 귀찮고...
-
작년 강x가 진짜 개좋았는디 3 0
강x와의 추억이 아직도 기억남..
-
제목만보고 글 판단하지마 6 3
똥글을 가장한 인증일수잇음
-
근대나왜6모대회10등이지 29 0
내가그렇게못봣다고
-
오직 토요코인만 사용함 나는 가난함
-
제얼굴이 프사랑 닮았나요 5 1
생각보다 그런소리를 꽤듣네요
-
낫배드인가
-
일본보다 멀어지면 비즈니스를 못타는 가난뱅이구나(O)
-
ox퀴즈 풀고 채점도 하시나요? 그리고 1단원 끝내고 바로 보시나용?
-
오래간만에 맞팔구 5 1
-
좀 늦은 6모 대회 글 9 3
오.. 위로 갈수록 천외천이네요.. 3만덕은 좋은 곳에 쓰겠습니다! 문과화이팅 이...
-
맞팔 하실분 16 0
댓 남기면 해드림
-
솔직히 지금 수특 표지 0 0
나를 깔보는 듯함 싸가지가 없어서 안풀고 싶뇨이
-
오옹 2 1
2등야호
-
확통 악깡버는 성공했는데 0 0
생윤은 극복이 안되네 수능날까지 맨땅에 헤딩하면 달라지려나
-
시대현강컨 병행 토일 제외 1일 1실모하면서 실모에서 틀린 문제 해당되는 단원 엔제...
-
-
아쉬운 수특 표지 후보 9 1
개인적으로 지금꺼보다 얘네가 더 취향임 고양이도있었네 ?
-
옴마야 4 1
잽싸게옷입기성공삼칠인권은지켜내따.
-
렌즈값 좀 9 1
30일에 62000원이면 싼건가
-
기어코 투데이 300을 찍음 13 1
오르비 줄일거임
-
이번에는 기필코 정상에
-
이 승리는 영원히 기억하마 너도 잘했다
-
갑자기 정병이 올라온다 10 2
정병 발사!
-
판사 배출 제일 많은 대학교가 10 3
성균관대구나 역시 명문 성대
-
공부일지(7/20) 3 2
메이저 N제들 유기한 죄 달게 받으라 7월 안에 어케 다 쳐내는 걸 목표로.....
-
재수생 대학라인좀 부탁드려요 0 0
7덮 언매 96 미적 77 영어 74 사문 42 지구 39 대충 13323이라치고...
-
저..첫경험이예요.. 5 1
옯만추는 처음이라..
-
분교도 뱃지 나옴? 3 0
고려대 세종캠 연세대 원주캠 여기도 그냥 뱃지줌?
-
7.20 공부 2 1
이매진 week2 국어오답노트 수학 강k4회 언매강의,생윤강의 공부 진짜...
-
그렇다고 해서 객관식 시험을 객관식 시험에 맞지 않게 준비하는것도 1 1
좋아하진 않음 예시) 비문학 납득하며 읽기, 문학에서 감상하고 공감하기 좀...
-
한방병원은 돈벌기힘들듯 4 1
방이 한개밖에 없어서 환자를 얼마 못받잖아
-
난 옵만추 한 번도 안해봄 13 1
어케하는거지..
-
약간 시험 출제경향이나 시험지특징으로 비벼서 성적만 올리려고 하는거 6 2
별로 안좋게보긴함 최대한 본질적 능지를 키우는걸 선호함 능지를 좋게하면 모든...
-
이거 향이 넘모 상큼쓰해서자꾸 입에 침고이는데 어카디
-
그 인스타에 뜌땨이라는 분이랑 프사가 같은데 우연인가요?
-
옯인싸 ㅁㅌㅊ 5 2
ㅇㅇ
-
14222고 0 0
국어 중간1 수학 낮4 세지 사문인데 이정도면 경북대 공대 가능한가요?
-
저 이모 왠지모르게삼칠이 마음에 드시는건지(?) 울집 놀러오시면삼칠 자고잇서도...
-
딮기 우승 스페인 우승 리트 대결 승리 완벽한 하루다
-
옯만추에 대한 고찰 7 0
실친이 오르비에 가입했고 내가 그 친구를 현실에서 보면 이건 옯만추인가?
-
햇반 사야하는데 0 0
자취는 죄다
-
옯인싸 ㅁㅌㅊ 3 2
방금 찍은거임
-
쪽지 보내봐 2 1
그냥 옯인싸인척 해보고싶음
-
잠온다 0 0
하암
-
보여주기식 공부에 매몰되면 안되는데 11 6
이게 또 나의 원동력이기도 하고.. 밸런스 맞추기 참 어렵네
C나 C++은 아닌데 typescript 로 tstl이라는 것을 구현한 국내 개발자가 계십니다. 타입스크립트쪽에서는 이미 글로벌에서 어느 정도 인지도가 있구요. 그 분의 결과물을 살펴보시면 지금 공부하시는 쪽이랑 좀 방향이 맞지 않을까 싶네요.
tstl이라면 그것도 일종의 라이브러리인가요...?
네 CPP의 STL을 Typescript로 구현한 라이브러리입니다.
물론 ts자체의 자료 구조로도 할려는 일을 다 할 수는 있지만, STL이 CPP에서 워낙 유명하다보니 STL에 포함된 자료구조를 Typescript로 구현한 분이 계십니다.
https://github.com/samchon/tstl
공부할 것들을 알려주셔서 너무 감사드립니다 ㅜㅜ 꼭 참고해보겠어요 :)