<aside> 1️⃣

문제 설명: 1021번 회전하는 큐

N개의 원소를 포함한 양방향 순환 큐에서 몇 개의 원소를 뽑으려고 함

큐에서 수행할 수 있는 연산

  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, …, ak 였던 것이 a2, …, ak가 됨
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

뽑으려는 원소를 주어진 순서대로 뽑는데 드는 2,3번 연산의 최솟값 구하기

</aside>

<aside> ✅

코드

#include <stdio.h>

int queue[100];
int front = 0, rear;

// 큐에서 몇 번째 인덱스에 있는지 반환
int place(int val, int size) {
    for (int i = 0; i < size; i++) {
        if (queue[(front + i) % 100] == val)
            return i;
    }
    return -1;
}

int main() {
    int N, M; // N <= 50, M <= N
    scanf("%d %d", &N, &M);

    rear = N;
    for (int i = 0; i < N; i++) {
        queue[i] = i + 1;
    }

    int count = 0;

    for (int i = 0; i < M; i++) {
        int target;
        scanf("%d", &target);
        int size = rear - front;
        int idx = place(target, size);

        // 2번 연산 (왼쪽으로)
        if (idx <= size / 2) { //어느쪽으로 돌리는게 더 빠른지 계산
            for (int j = 0; j < idx; j++) {
                int temp = queue[front];
                for (int k = front; k < rear - 1; k++) {
                    queue[k] = queue[k + 1];
                }
                queue[rear - 1] = temp;
                count++;
            }
        }
        // 3번 연산 (오른쪽으로)
        else {
            for (int j = 0; j < size - idx; j++) {
                int temp = queue[rear - 1];
                for (int k = rear - 1; k > front; k--) {
                    queue[k] = queue[k - 1];
                }
                queue[front] = temp;
                count++;
            }
        }

        // 1번 연산 (뽑기)
        front++;
    }

    printf("%d", count);
    return 0;
}

image.png

</aside>

<aside> 2️⃣

문제 설명: 2075번 N번째 큰 수

NxN의 표에 채워진 모든 수는 자신의 한 칸 위의 수보다 크다

N번째 큰 수를 찾는 프로그램 작성

<aside> ✅

코드

#include <stdio.h> 

typedef struct {
	int data;
} node;

typedef struct {
	node arr[1500 * 1500 + 1];
	int size;
} HEAP;

HEAP h;

void push(int data)
{
	int i = ++(h.size); //힙 사이즈 증가, 삽입할 위치 인덱스 설정

	//부모 노드와 비교하면서 위로 올라감
	while ((i != 1) && (data > h.arr[i / 2].data)) {
		h.arr[i].data = h.arr[i / 2].data; //부모를 자식으로 내림
		i /= 2; //부모로 이동
	}
	h.arr[i].data = data; //올바른 위치에 삽입
}

int pop()
{
	int root = h.arr[1].data; //루트(최댓값)를 저장
	int temp = h.arr[(h.size)--].data; // 마지막 원소 임시 저장, 사이즈 줄임

	int parent = 1;
	int child = 2;

	//temp 값을 아래로 내려가며 올바른 위치 찾기
	while (child <= h.size){
		//오른쪽 자식이 더 크면 오른쪽으로 이동
		if ((child < h.size) && (h.arr[child].data < h.arr[child + 1].data)) {
			child++;
		}

		//자식보다 크면 멈춤
		if (temp >= h.arr[child].data)
			break;

		//자식을 위로 올리고
		h.arr[parent].data = h.arr[child].data;
		parent = child;
		child *= 2; //다음 자식
	}
	h.arr[parent].data = temp; //올바른 위치에 temp 삽입

	return root; //제거된 루트 값 반환
}

int main(){
	int n;
	scanf("%d", &n); //N 입력

	h.size = 0; //힙 초기화

	int num;
	for (int i = 0; i < n * n; i++){
		scanf("%d", &num); 
		push(num); //힙에 삽입
	}

	//N번째 큰 수 찾기:
	while (h.size > n * n - n + 1){
		pop();
	}
	
	printf("%d", pop());//마지막으로 pop한 것
	return 0;
}

image.png

</aside>