c언어 20291번 파일정리 (백준)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define P 37
#define M 1000000007
#define m 64321

int n,i,j,h,v,l;
char txt[101],ext[101],*sTable[m];
int nTable[m]={},sortCnt=0;

int cmp(const void *a, const void *b) { //해쉬값을 이용하여 문자열을 불러온 다음
	return strcmp(sTable[*(int*)a],sTable[*(int*)b]); //사전 순 비교
}

void hash(char * s) { //해쉬값 만들기
	long long a=0,b=1;
	l=0;
	while(*s) {
		long long c=(*s-'a'+1);
		a=(a+c*b)%M;
		b=(b*P)%M;
		++s;
		++l;
	} 
	v = a%m;
}

int main(void) {
	scanf("%d",&n);
    int sort[n]; //사용된 해쉬값 저장하기
	for(i=0;i<n;i++) {
		scanf("%[^.]%*c%s",txt,ext); //name.extension 으로 구분해서 입력받기
		hash(ext); //해쉬값 구하기
		h=1; //1이면 새로 들어오는 문자열, 0이면 이미 해쉬테이블에 있던 값을 의미
		if(nTable[v]) { //이미 문자열이 있다면
			if(!strcmp(ext,sTable[v])) h=0; //자기자신인지 확인
			else { //아니라면 (충돌 발생)
				while(1) {
					++v; //1증가
					if(v==m)v=0; //범위 초과시 0으로
                    if(nTable[v]) { //다른 누군가가 있음
                      if(!strcmp(ext,sTable[v])) {h=0;break;}  //자기 자신이면 반복문 종료
                    } else break; //없음, 여기에 들어가면 됨, 반복문 종료
				}
			}	
		} 
		if(h) { //새로운 값을 해쉬 테이블에 삽입
			nTable[v]=1;
			sTable[v] = (char*) malloc(l+1);
			strcpy(sTable[v],ext);
			sort[sortCnt++]=v;
		} else ++nTable[v]; //중복값인 경우
	}
	qsort(sort,sortCnt,4,cmp); //문자열 사전 순으로 해쉬값 정렬
	for(i=0;i<sortCnt;i++) { //정렬된 해쉬값으로
        printf("%s %d\n",sTable[sort[i]],nTable[sort[i]]); //문자열과, 개수 출력
        free(sTable[sort[i]]); //동적할당 해제
    }
	
}

 

풀이 : 해쉬 테이블

 

stdio.h

string.h : strcmp (문자열 비교), strcpy(문자열 복사)

stdlib.h : 동적할당, qsort

을 이용하여 조그마한 해쉬테이블을 구현해보았습니다.

 

M은 long long 값을 벗어나지 않도록 둔 큰 소수입니다.

m은 해쉬테이블의 크기입니다. 문제에서 최대 5만개의 파일이 주어지고, 최악의 경우 5만개의 각기 다른 확장자가 올수 있음에 염두해 두고 대충 64321로 잡았습니다. 50000으로 하면 충돌이 너무 많이 발생할 것 같았습니다.

 

해쉬값이 같은 경우, 1씩 증가시키고, 비어있다면 추가, 비어있지 않지만 만약 같은 문자열일수도 있으므로 strcmp으로 한번 비교를 시켰습니다. (없는 곳이 나오거나, 같은 문자열이 나올때 까지 1씩 증가시키는 것을 반복합니다)

 

해쉬테이블을 전부 훑어서, 값이 들어있는 곳의 값을 가져오는것은 시간이 아깝기 때문에

sort[]라는 배열에, 새로운 문자열이 테이블에 추가될때마다, 그때의 해쉬값을 저장했습니다.

이 sort[]에 있는 값으로, 마지막 조건인 "사전순으로 정렬"을 쉽게 해결했습니다.

 

정렬은 qsort을 이용했습니다.

 

---

scanf("%[^.]%*c%s",txt,ext); 

 

여기서 %*c 에 있는 *는 입력은 받되 무시하라는 의미입니다.

%[^.] 이것은 .을 제외한 모든 문자들을 입력받는다는 의미입니다.

 

고로 이름.확장자 로 주어지는 입력에서

%[^.] <- 이름

%*c <- .

%s <- 확장자

 

이렇게 들어갑니다.