c언어 16139번 인간-컴퓨터 상호작용 (백준)

 

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

16139번: 인간-컴퓨터 상호작용

 

 

 

 

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

int main(void)
{
	char arr[200001]; //문자열을 담을 배열
	scanf("%s", arr); //문자열 입력
	int len = strlen(arr); //입력받은 문자열의 길이
	int a[27][len]; //알파벳은 26개다.  2차원 배열 선언
	
	for(int i = 0; i<len; i++) //문자열에 무슨 알파벳이 있는지, 한칸 한칸 이동하면서 구하기
	{	
		for(int j = 0; j<27; j++) a[j][i] = 0; // 이차원 배열 a의 모든값을 0으로 초기화
		int tmp = arr[i]-97; //a ASCII : 97(d) //특정 문자가 있으면
		a[tmp][i]++; //a[특정문자][그 때의 문자열의 길이]을 1 증가 시킨다.
	}
	
	for(int i = 1; i<len; i++) //이차원 배열 a의 알파벳에 따른 부분합들 구하기
	{
		for(int j = 0; j<26; j++) //a~z
		{
			a[j][i] += a[j][i-1]; 
		}
	}
	
	
	int q = 0;
	scanf("%d", &q); //몇 번?
	
	while(q>0)
	{
		char ch = 0; //무슨 문자?
		int x, y; //범위
		scanf(" %c%d%d", &ch, &x, &y); //입력받음
		if(x == 0) printf("%d\n", a[ch-97][y]); //x가 0이면 y의 부분합만 출력하면 됨
		else printf("%d\n", a[ch-97][y]-a[ch-97][x-1]); //부분합끼리 빼면, 범위 내 합을 알 수 있음
		q--;
	}

	return 0; //main 함수 종료
}

 

 

• 풀이

1) 변수 선언

문자열을 담을 배열 (char arr[200001]) 을 선언하고 입력받고, 입력받은 문자열의 길이를 구하고, 알파벳과 몇번 째의 부분합을 담기 위한 이차원 배열도 선언한다.

 

2) 어디에 무슨 알파벳이 있는지 구하기

for을 이용하여, 먼저 부분합을 담기위한 이차원 배열을 0으로 초기화하면서, 길이을 1씩 증가시키면서, 거기서의 알파벳의 이차원 배열의 값을 1로 바꾼다.

 

3) 알파벳들의 길이에 따른 부분합 구하기

for을 이용하여, 각각 알파벳들마다, 길이에 따른 부분합을 구한다.

 

4) 몇 번 답변 할지를 입력받는다.

 

5) 알파벳과, 범위를 입력받고, 그에 대한 부분합을 출력한다!