Daily Algorithm - 기억력 테스트 9

문제

진짜 오랜만에 주현이 엄마는 기억력 테스트를 하기로 했다.

주현이가 많이 컸기 때문에 이제 숫자만 가지고 테스트하기엔 부족하다.

이번에도 N개의 숫자를 불러주고, M개의 질문을 한다.

처음에 [단어]와 [숫자]를 불러주고, 질문으로 [단어]를 물어보면 해당 단어의 [숫자]를 말하는 것이다.

그런데 불러 줄 때 같은 [단어]가 나오는 경우 [이전 단어]의 [숫자]에 [현재 숫자]를 더해야 한다.

예를 들어 "ddobot 3" , "poketmon 5", "ddobot 7"을 불러 주고, 질문으로 "ddobot"을 물었을 경우 3+7인 10을 답해야 한다.

이번에는 포켓몬 썬&문  카드 풀 팩이 걸려 있다. 주현이가 잘 할 수 있도록 도와주자.

입력

첫째 줄에 N과 M이 입력된다.(1<=N,M<=100,000)

둘째 줄부터 N줄 동안 문자열 S와 정수 k가 입력된다. 

그 다음 M줄 동안 질문 Q가 문자열로 입력된다. 만약 부르지 않았던 단어를 질문하는 경우 0을 출력한다.

(S, Q는 100글자 이하 영어 소문자 알파벳으로만 구성, k는 10이하의 자연수)

출력

질문에 맞는 [누적 숫자]를 한줄에 하나씩 출력한다.

예제 입력

3 4
ddobot 3
poketmon 5
ddobot 7
ddobot
poketmon
ddobot
hellocarbot

예제 출력

10
5
10
0

풀이

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct answer {

char name[100];

int num;

}answer;

int main()

{

int n, m, num;

char name[100];

scanf("%d %d", &n, &m);

answer *arr = malloc(sizeof(answer) * 250);

for (int i = 0; i < n; i++)

{

scanf("%s %d", name, &num);

int idx = 0;

for (int j = 0; j < strlen(name); j++)

{

idx += (int) name[j] - 97;

}

if (strcmp(arr[idx].name, name) == 0)

{

arr[idx].num += num;

}

else

{

strcpy(arr[idx].name, name);

arr[idx].num = num;

}

}

for (int i = 0; i < m; i++)

{

scanf("%s", name);

int idx = 0;

for (int j = 0; j < strlen(name); j++)

{

idx += (int) name[j] - 97;

}

if (strcmp(arr[idx].name, name) == 0)

{

printf("%d\n", arr[idx].num);

}

else

{

printf("0\n");

}

}

free(arr);

}

기억력 테스트를 진행하는 배열 자체는 구조체로 간단하게 구현이 가능하다.

하지만 구조체 배열을 for문으로 일일히 접근해서 있는 이름인지 확인할 경우 시간 초과가 발생하게 된다.

시간안에 문제를 해결하기 위해 배열의 인덱스를 해당 문자의 아스키 코드 값을 이용해서 만들어낸 값으로 지정해줬다.

있는 문자인지 확인하거나, 해당 수를 확인할 때 반복문으로 일일히 확인할 필요 없이 바로 해당 인덱스로 접근할 수 있어 시간 초과를 해결할 수 있다.

문제 출처 : http://codeup.kr/JudgeOnline/problem.php?id=3170