BOJ 10845, 18258 : 큐, 큐2

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/10845

www.acmicpc.net/problem/18258

 

큐, 큐2 문제는 같지만 명령의 수가 다르다.

큐는 N이 작아서 적당히 풀어도 통과할 수 있다.

큐2 기준으로 풀려면 모든 명령어를 O(1)이 되도록 풀어야 한다.

 

큐도 메모리만 넉넉하게 잡으면 스택처럼 배열로만 풀 수 있다.

스택과 다른 점은 pointer가 2개 필요하다.

 

큐에서 push할 때 write pointer를 증가시키고, pop할 때는 read pointer를 증가시키면 큐가 된다.

그리고 read와 write의 차이가 queue의 사이즈가 된다.

 

현재 queue의 뒤에 값을 저장해야 하므로 wp에 값을 저장하고 증가시킨다.

 

queue[wp] = input, wp++;

→ queue[wp++] = input;

 

현재 queue에 가장 앞에 있는 값은 rp에 있으므로, output에 저장하고 증가시킨다.

 

output = queue[rp], rp++;

→ output = queue[rp++];

 

스택에서 pop을 할 때는 sp가 0인지 체크하는 것과 비슷하게,

큐에서는 wp - rp가 0인지 체크하면 된다.

 

#include <stdio.h>

int queue[2000000 + 50000];
int rp, wp;

int mystrcmp(const char *a, const char *b)
{
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

int main(void)
{
	int in, N;
	char str[10];

	scanf("%d", &N);

	for (int i = 0; i < N;i++)
	{
		scanf("%s", str);

		if (mystrcmp(str, "push") == 0)
		{
			scanf("%d", &in);
			queue[wp++] = in;
		}
		else if (mystrcmp(str, "pop") == 0) printf("%d\n",(wp == rp) ? -1 : queue[rp++]);	
		else if (mystrcmp(str, "size") == 0) printf("%d\n", wp - rp);
		else if (mystrcmp(str, "empty") == 0) printf("%d\n", wp == rp);
		else if (mystrcmp(str, "front") == 0) printf("%d\n", (wp == rp) ? -1 : queue[rp]);
		else if (mystrcmp(str, "back") == 0) printf("%d\n", (wp == rp) ? -1 : queue[wp - 1]);
	}
    
    return 0;
}