[C] 백준 - 16139번: 인간-컴퓨터 상호작용

3월 24일(금) - 누적 합 (16139번)

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

char string[200001];

int main(void)
{
	int q, start, end;
	char ch;

	scanf("%s", string);
	scanf("%d", &q);

	for (int i = 0; i < q; i++)
	{
		int count = 0;
		scanf(" %c %d %d", &ch, &start, &end);

		for (int j = start; j <= end; j++)
		{
			if (string[j] == ch)
			{
				count++;
			}
		}
		printf("%d\n", count);
	}

	return 0;
}

1. 위의 풀이를 토대로 예제1은 제대로 실행되었지만, 부분 성공

-> 입력받은 문자열에서 하나하나의 문자가 몇 번 나왔는지를 표현하는게 불가능하다고 판단

-> 또한 시간초과도 발생할 것 같다고 판단

-> 알파벳순서대로 크기가 26인 배열을 만든뒤, 새롭게 등장하는 문자 하나마다 +1을 해주는 방향으로 풀이 수정

 

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

char string[200001];
int alphabet[26][200001] = { 0, };

int main(void)
{
	int q, start, end;
	char ch;

	scanf("%s", string);
	scanf("%d", &q);

	int len = strlen(string);
	for (int i = 0; i < len; i++)
	{
		alphabet[string[i] - 97][i] += 1;
	}

	for (int i = 0; i < q; i++)
	{
		scanf(" %c %d %d", &ch, &start, &end);

		if (start == 0)
		{
			printf("%d\n", alphabet[ch - 97][end]);
		}
		else
		{
			printf("%d\n", alphabet[ch - 97][end] - alphabet[ch - 97][start - 1]);
		}
	}

	return 0;
}

2. 예제 1번을 입력하면,

a 0 5   -> 0

a 0 6   -> 1

a 6 10 -> 1

a 7 10 -> 0

이처럼 시작하는 포인트가 0이 아닌 경우에는 잘못된 출력값이 나오고 있다

-> 누적 합이 제대로 더해지지 않고 있는 것 같다는 판단

 

for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < 26; j++)
		{
			alphabet[j][i] += alphabet[j][i - 1];
		}
	}

3. 누적 합을 구하기 위해서 바로 위의 풀이과정에다가 추가한 부분

-> 추후 복습 필요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

char string[200001];
int alphabet[26][200001] = { 0, };

int main(void)
{
	int q, start, end;
	char ch;

	scanf("%s", string);
	scanf("%d", &q);

	int len = strlen(string);
	for (int i = 0; i < len; i++)
	{
		alphabet[string[i] - 97][i] += 1;
	}

	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < 26; j++)
		{
			alphabet[j][i] += alphabet[j][i - 1];
		}
	}

	for (int i = 0; i < q; i++)
	{
		scanf(" %c %d %d", &ch, &start, &end);

		if (start == 0)
		{
			printf("%d\n", alphabet[ch - 97][end]);
		}
		else
		{
			printf("%d\n", alphabet[ch - 97][end] - alphabet[ch - 97][start - 1]);
		}
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ