반응형
B형 reference 코드의 우선순위 큐는 최소 힙만 주어져있다.
코드 변경을 최소화해서 구조체 힙을 풀어보자.
reference 코드에서 우선순위를 비교하는 곳을 구조체에 대한 우선순위로 수정한다.
1) heapPush의
while (current > 0 && heap[current] < heap[(current - 1) / 2])
2) heapPop의
child =
heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
3) heapPop의
if (heap[current] < heap[child])
{
break;
}
A < B 부분을 isMin(A, B)로 변경하면 된다. (구조체 우선순위 비교 함수)
국영수 문제의 경우 우선순위는 아래와 같다.
int isMin(HEAP a, HEAP b) /* int -> HEAP */
{
if (a.kr > b.kr) return 1;
if (a.kr == b.kr)
{
if (a.en < b.en) return 1;
if (a.en == b.en)
{
if (a.math > b.math) return 1;
if (a.math == b.math)
{
if (mystrcmp(a.name, b.name) < 0) return 1;
}
}
}
return 0;
}
그리고 모든 heap의 type int에 대해 구조체 type HEAP으로 변경해주면 된다.
함수에 넘겨주는 heap, 교체에 필요한 temp 모두 HEAP으로 변경하였다.
#include <stdio.h>
int N;
typedef struct st
{
char name[15];
int kr;
int en;
int math;
}HEAP;
HEAP heap[100100]; /* int -> HEAP */
int heapSize;
void mystrcpy(char *a, const char *b)
{
while (*a++ = *b++);
}
int mystrcmp(const char *a, const char *b)
{
while (*a && *a == *b) ++a, ++b;
return *a - *b;
}
int isMin(HEAP a, HEAP b) /* int -> HEAP */
{
if (a.kr > b.kr) return 1;
if (a.kr == b.kr)
{
if (a.en < b.en) return 1;
if (a.en == b.en)
{
if (a.math > b.math) return 1;
if (a.math == b.math)
{
if (mystrcmp(a.name, b.name) < 0) return 1;
}
}
}
return 0;
}
int heapPush(HEAP* heap, int& heapSize, HEAP value) /* int -> HEAP */
{
heap[heapSize] = value;
int current = heapSize;
while (current > 0 && isMin(heap[current], heap[(current - 1) / 2])) /* 우선순위 변경 */
{
HEAP temp = heap[(current - 1) / 2]; /* int -> HEAP */
heap[(current - 1) / 2] = heap[current];
heap[current] = temp;
current = (current - 1) / 2;
}
heapSize = heapSize + 1;
return 1;
}
int heapPop(HEAP* heap, int& heapSize, HEAP *value) /* int -> HEAP */
{
*value = heap[0];
heapSize = heapSize - 1;
heap[0] = heap[heapSize];
int current = 0;
while (current * 2 + 1 < heapSize)
{
int child;
if (current * 2 + 2 == heapSize)
{
child = current * 2 + 1;
}
else
{
child = /* 우선순위 변경 */
isMin(heap[current * 2 + 1], heap[current * 2 + 2]) ? current * 2 + 1 : current * 2 + 2;
}
if (isMin(heap[current], heap[child])) /* 우선순위 변경 */
{
break;
}
HEAP temp = heap[current]; /* int -> HEAP */
heap[current] = heap[child];
heap[child] = temp;
current = child;
}
return 1;
}
int main(void)
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
HEAP x;
int kr, en, math;
char str[15];
scanf("%s %d %d %d", str, &kr, &en, &math);
x.kr = kr;
x.en = en;
x.math = math;
mystrcpy(x.name, str);
heapPush(heap, heapSize, x);
}
for (int i = 0; i < N; i++)
{
HEAP tmp;
heapPop(heap, heapSize, &tmp);
printf("%s\n", tmp.name);
}
return 0;
}
실제 시험에서는 register도 추가해주자.
반응형
'알고리즘 > [PRO] 삼성 SW 역량 테스트 B형' 카테고리의 다른 글
BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 (0) | 2021.07.03 |
---|---|
우선순위 큐 갱신 - B형 Reference 코드 (0) | 2021.06.09 |
최대 힙, 절댓값 힙 - B형 Reference 코드 (우선순위 큐) (0) | 2021.06.05 |
최소 힙 - B형 Reference 코드 (우선순위 큐) (0) | 2021.06.05 |
인라인(inline) 함수 - 삼성 SW 역량 시험 환경 (0) | 2021.05.19 |
댓글