9375 : Incognito

네르기·2021년 8월 21일

생각 조합 해쉬맵

알고리즘

목록 보기

24/76

어떤 문제인가?

해쉬맵을 이용해 조합의 개수를 찾는 문제다.

아니 이게 왜 시간초과??

매우 개빡치는 경험을 한 문제 중 하나다.
문제를 보고 해쉬맵을 써야한다는 건 알았다. 그래서 C로 해쉬맵을 구현해서 써봤다. 다음은 내 코드다.

#include <stdio.h>

int h(char *s) {
    int i=1;
    unsigned long c=0;
    while(s[i-1]!='\0') {
        c+=((s[i-1]-96)*i*i)%1024;
        i++;
    }
    return c%1024;
}

int main() {
    int N,T,S=1,i=0,j=0,H[1024]={0},F[30]={0},k=0,t;
    char X2[10]={0},_[1];
    scanf("%d",&T);
    for(i=0;i<T;i++) {
        scanf("%d",&N);
        S=1;
        for(j=0;j<k;j++) F[j]=H[F[j]]=0;
        k=0;
        for(j=0;j<N;j++) {
            scanf("%s%s",_,X2);
            t=h(X2);
            if(!H[t]) F[k++]=t;
            H[t]+=1;
        }
        for(j=0;j<k;j++) S*=(H[F[j]]+1);
        if(!k) S=0;
        else S-=1;
        printf("%d\n",S);
    }
}

코드를 3번이나 바꾼게 이 정도인데 시간 초과란다. 어이가 없었다.
지금 생각해보니 종류를 나타내는 문자열 길이가 한도가 없었던 것 같은데, 이건 원인이 아닌 것 같다. 하여튼간에 C를 이용해 접근하는 방식은 포기했다.

파이썬

이게 안됐다면 다 때려치고 다른 거 풀려고 했다. 틀린 이유를 정확히 알 수 없으니 너무 답답했다.

import sys

D, S = {}, 1
T = int(input())
for i in range(0, T):
    N = int(input())
    D, S = {}, 1
    for j in range(0, N):
        _, c = sys.stdin.readline().split()
        if c not in D:
            D[c] = 0
        D[c] += 1
    for v in D.values():
        S = S*(v+1)
    print(S-1)

그리고 이건 됐다. 다행인지 불행인지.

남들은 어떻게 풀었나 : C

해시맵 구현을 2중 배열로 해서 푼 사람이 다수였다.
아 ㅋㅋㅋ 이럴줄 알았으면 나도 이렇게 할 걸 그랬다.

#include <stdio.h>
#include <string.h>

int main(void) {
	int T;
	int N;
	int k;
	int ans;
	int kind[30];
	char cloth[30][30];
	char trash[30];
	char tmp[30];
	int flag;
	

	scanf("%d", &T);
	for (int z = 0; z < T; z++) {

		//의상의 종류(k)와 각각 몇개씩인지 kind[k]를 구한다.
		scanf("%d", &N);
		k = 0;
		for (int i = 0; i < N; i++) {
			flag = 0;
			scanf("%s %s", trash, tmp);
			for(int j=0; j<k; j++)
				if (!strcmp(cloth[j], tmp)) {
					flag = 1;
					kind[j]++;
					break;
				}
			if (!flag) {
				kind[k] = 1;
				strcpy(cloth[k++], tmp);
			}

		}
		
		ans = 1;
		for (int i = 0; i < k; i++)
			ans *= (kind[i] + 1);

		printf("%d\n", ans - 1);



	}
}