어떤 문제인가?

큐에 있는 값을 이용해 푸는 문제. 우선순위 큐를 써도 된다.

내 풀이

큐에 이미 값이 주어진 고로, 값 삭제 연산 및 비교만 주로 했다. 다른 분들의 코드를 보니 front, rear를 둘 다 둔 경우가 많던데, 값을 추가할 일이 없으니 front만 남겨도 된다.

#include <stdio.h>

int Q[100],s=0,f=0,c=0,m;

int k() {
    int i;
    for(i=0;i<s;i++) {
        if(Q[f]<Q[i]) {
            f=(f+1)%s;
            return 0;
        }
    }
    if(f==m) return 1;
    for(i=f+1;i<s;i++) Q[i-1]=Q[i];
    s--; m=m>f?m-1:m; f%=s; c++;
    return 0;
}

int main() {
    int T,n,i;
    scanf("%d",&T);
    while(T>0) {
        scanf("%d%d",&n,&m); s=n;
        for(i=0;i<n;i++) scanf("%d",&Q[i]);
        while(s>1) {
            if(k()) break;
        }
        printf("%d\n",++c);
        T--; f=c=0;
    }
    return 0;
}

나 같은 경우에는 큐 삭제를 무식한 방법으로 진행했다.
front보다 앞에 있는 모든 배열의 원소에 대해, 1칸씩 앞으로 전부 끌어왔다.

다른 분들의 풀이

큐 없이 리스트로만 풀 수 있다. 최댓값부터 탐색하면서.

#include<stdio.h>
int main()
{
	int t,n,m,f[101],p[10],i,c,v;
	scanf("%d",&t);
	while(t>0)
	{
		c=0;
		for(i=0;i<10;i++)
			p[i]=0;
		scanf("%d %d",&n,&m);
		for(i=0;i<n;i++)
		{
			scanf("%d",&f[i]);
			p[f[i]]++;
		}
		v=9;
		while(i!=m)
		{
			while(p[v]==0)
				v--;
			for(i=0;i<n;i++)
			{
				if(f[i]==v)
				{
					p[v]--;
					c++;
					if(i==m)
						break;
					while(p[v]==0)
						v--;
				}
			}
		}
		printf("%d\n",c);
		t--;
	}
}

dranger97님의 소스
-> https://www.acmicpc.net/source/19324567

큐를 완전히 지워버려야 하는지(내 방법처럼), 그럴 필요 없이 임의의 값으로 덧씌워 지워도 되는지를 확인하는 연습이 필요한 것 같다. 둘 다 구현 방법이 다르지만 큐 원소의 제거방법이라는 점에선 같으니까 말이다.