컴공 일기218
게시글 주소: https://dev.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를 선물하세요.
-
근데 더프 수학선택 범위 좁은건 3모대비라하면 이해되는데 4 3
투과목 << 얘넨 3모에도 안나오는데 전범위로 하면 될걸 왜 꾸득꾸득 초반부만 넣는거임
-
알림창 개폭력적이네 9 6
-
개강 3주차...아직 후배 얼굴도 본적없음
-
시발 뭘 할 수가 없네 9 1
친구 없어도 그래도 고대 왔으니 합응까진 갈까 했는데 허리 이 시발롬 좆도 안낫고 더 아파짐 아오
-
음주체스숙취수학 1 0
왜효고ㅓ좋냐
-
옾붕이들은 영어듣기 잘하나요 9 0
듣기 살면서 한번도 안툴린 사람 많으려나영듣칼럼 쓰려 하는데 수요 있으려나...
-
와 시벌 이게 얼마만인지 모르겟다 한달만에 같이 밥먹는거같은데 두달인가?
-
본인은 메인 두 번 가봄 3 1
한 번은 평가원 피셜 확정 등급컷 (영어) 네이버 블로그 감성 글로 가봤고 한 번은...
-
역시 약대생 3 1
난 시간 꽉꽉 채워 풀어서 88점인데
-
3덮 미적 풀어봤다 15 2
이렇다 전 글에서 맞춘사람 5000덕 보내줄게 생각보다 잘나왔네 22 30은 걍...
-
3모 ㅈ된거같으면 개추. 3 3
ㄱㄱ
-
어스름 내린 언덕 너머로 푸른 융단이 조용히 깔리면 4 1
수줍게 눈을 뜨는 작은 별들 사이로 깊고 아득한 밤이 피어납니다.
-
JMS 유튜버 댓글 근황 1 2
빨리 JMS에서 탈출하길 빕니다
-
대학간 오르비언 특 8 3
2월 말 ~ 3월 첫째주까진 재밌다~~ 하면서 안들어오더니 3월 둘째주부턴 외롭다...
-
나 분명 학기중엔 0 0
새르비를 안할줄알았는데ㅔㅔㅔ 옯창이 맞는것인가?
-
체언 수식 부사
-
새르비ing 0 0
손 ㄱㄱ
-
지방대 궁금한점 질문받음 9 0
옯인원들에겐 관심없을수있지만 25수능때 66584로 지방대 빵노리고 붙었음...
-
독서 제대로 이해한 지문이 없었음... 심지어 마킹 안 하고 1분 초과됨 3모 5일...
-
아빠 잔다 2 1
잔디wwwwww
-
재작년에 수능봐서 백분위 97 받고 대학 다니다가 올해 다시 수능 준비 중인데 생명...
-
3연강으로맞고 0 0
8:30~17:30당하니까죽겠다
-
여기다전화해줘 0 1
119 너 때문에 내 심장이 멎었어
-
행복해요 8 0
-
현역이때 생윤 말아먹어서 재수때 정법하서 3나왔어요 다시 생윤으로 돌아갓?...
-
글리젠 진짜 없네 2 0
내가아는 오르비가맞냐
-
ㅇㅇ
-
그것이 문제로다
-
오르비 굿나잇 ~ 7 1
피곤해뒤지겟다 오답은 내일 할게
-
얘네가 진선여고 숙명여고에 있었으면 내신 몇 뜰까요? 7 0
옛동네인 영등포에 사는 초등동창인 여사친들인데 한 아이는 영등포 공학 좆반고에서...
-
N제 먼저?? 0 0
수1 스블 다 들었고 수2,확통 실점개념 반정도 들었는데 수2,확통까지 실전개념 다...
-
08) 오늘의 공부인증!! 10 1
그냥 너무 심란함 모든것에 대해서 ㅠㅠ
-
ㄹㅇㅋㅋ
-
에효 못생긴 옵붕이들 ㅉ 0 1
심지어 공부도 못하는 말이야
-
새르비 최강의 남자 3 1
쌍윤왜어려움
-
3섶 화1 45 4 0
물2는...예...
-
5시긴40분뒤에일어니야더ㅣㅁ 2 2
습박
-
오늘 저녁 ㅁㅌㅊ? 4 1
돼지 되는 중 ...ing
-
새르비의라이징스타 0 0
설국문쟁취
-
한국 kf21 보라메=>뭔가 문제 있어보이고 그렇게 안 쌜거 같음 미국 f22 =>...
-
김기현쌤 아이디어 0 0
작수 4이고 이번에 확통으로 바꿨습니더 확통은 시발점 듣고있는데 수1 수2를 어느...
-
조해공 과잠 봤을 때였음 조선해양공학과 <- 개틀딱같음 Naval...
-
이거 개쩌는 공부법인듯 2 1
1주마다 문제집 제끼고 오르비에 인증하기 앉아있는 시간은 같지만 공부량 ㅈㄴ 늘어난게 체감이 됨
-
윤사 코드원 샀음 1 2
윤사 개박살 났으니까 그래도 김종익 플러스 해서 코드원까지 하려고..
-
전화하고싶다 3 0
누구든좋으니까
-
작년에 2 0
2월부터 수능까지 새르비에 항상 있었던 사람이 있음
-
소아과 의사 누구였지 6 0
오르비언 ㅇㅅㅇ
-
한 달 뒤 새르비 상황 1 3
제목:진짜 다 뒤1졌냐? 2분전 조회수 8 작성자 수능 ㅈ된 설의적표현 내용:
-
???
-
수1 자작 0 1
수열 문제입니다. 거의 국밥 유형인 케이스 분류 문제에요. 오류 발견하시면...
C나 C++은 아닌데 typescript 로 tstl이라는 것을 구현한 국내 개발자가 계십니다. 타입스크립트쪽에서는 이미 글로벌에서 어느 정도 인지도가 있구요. 그 분의 결과물을 살펴보시면 지금 공부하시는 쪽이랑 좀 방향이 맞지 않을까 싶네요.
tstl이라면 그것도 일종의 라이브러리인가요...?
네 CPP의 STL을 Typescript로 구현한 라이브러리입니다.
물론 ts자체의 자료 구조로도 할려는 일을 다 할 수는 있지만, STL이 CPP에서 워낙 유명하다보니 STL에 포함된 자료구조를 Typescript로 구현한 분이 계십니다.
https://github.com/samchon/tstl
공부할 것들을 알려주셔서 너무 감사드립니다 ㅜㅜ 꼭 참고해보겠어요 :)