c언어 2910번 빈도 정렬 (백준)

#include <stdio.h>
int main(void) {
	int n,c,i,j,x,y,z,g,p=0;
	scanf("%d %d",&n,&c);
	int a[n][3];
	for(i=0;i<n;i++) {
		y=0;
		scanf("%d",&x);
		for(j=0;j<p;j++) {
			if(a[j][0]==x) {
				++a[j][2];
				y=1;
				break;
			}
		}
		if(y==0) {
			a[p][0]=x;
			a[p][1]=i;
			a[p][2]=1;
			++p;
		}
	}
	
	g=p>>1;
	while(1) {
		if(!(g&1)) ++g;
		for(i=g;i<p;i++) {
			x=a[i][0];y=a[i][1];z=a[i][2];
			for(j=i-g;j>=0;j-=g) {
				if(z>a[j][2] || (z==a[j][2] && y<a[j][1])) {
					a[j+g][0]=a[j][0];
					a[j+g][1]=a[j][1];
					a[j+g][2]=a[j][2];
				} else break;
			} 
			a[j+g][0]=x;
			a[j+g][1]=y;
			a[j+g][2]=z;
		}
		if(g==1) break;
		g>>=1;
	}
	for(i=0;i<p;i++) for(j=0;j<a[i][2];j++) printf("%d ",a[i][0]);
}

 

풀이 : 집합과 맵

 

map을 구현하려면 red-black tree을 구현해야 하나, 그정도의 실력은 되지 않으며, 자료가 별로 주어지지 않기 때문에 배열로 가짜 map을 만들었습니다.

(탐색시간이 O(n)으로 비효율적입니다)

 

1. n,c 을 입력받습니다.

2. a[n][3] 이라는 배열을 만듭니다. 0번째는 값, 1번째는 들어온 순서 index, 2번째는 같은 값이 몇개 들어왔는지 입니다

3. 정수들을 입력받고 map을 구성합니다. 없는 key라면 새롭게 만들어주고, 이미 있던 key 라면 갯수만 갱신해줍니다.

4. 정렬을 합니다. 기준은 앞에있는 요소가 갯수가 더 많거나, 갯수가 동일하되 입력받은 순서가 빠르도록 정렬합니다.

5. 정렬된 맵을 가지고 갯수만큼 key 값을 출력합니다.

 

https://www.acmicpc.net/problem/2910