글 읽기 - 시간초과 좀 도와주세요

kkw564 7년 전 0

어떻게 더 최적화 해야할지 감이 잘 오지 않습니다..

시간초과를 어떻게 해야 극복할 수 있을까요?

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

vector<int> q[25];
char str[300001][21];
int strLen[300001];

int main()
{
	int n, k;
	long long int cnt = 0;
	int charlen;
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++)
	{
		scanf("%s", str[i]);

		charlen = strlen(str[i]);
		q[charlen].push_back(i);
		strLen[i] = charlen;
	}

	for (int i = 0; i < n; i++)
	{
		// 글자 크기를 알아내어 큐를 들어간다.
		int idx = strLen[i];

		// 해당하는 큐에 첫번째 값의 순서를 알아 낸 뒤 pop
		int order;
		int idxlen = q[idx].size();

		order = q[idx][0];
		q[idx].erase(q[idx].begin() + 0);
		if (q[idx].size() == 0)
			continue;

		int len = q[idx].size();
		// 해당하는 큐의 크기 내에서 y - x <= k 인것을 찾아낸다.
		for (int j = 0; j < len; j++)
		{
			if (j < q[idx].size() && q[idx][j] - order <= k)
				cnt++;
			else
				break;
		}
	}

	printf("%lld", cnt);

	return 0;
}

chogahui05 7년 전 1

kkw님 알고리즘을 분석해 봅시다.

CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

이 경우 q에는 다음과 같은 내용이 들어갑니다.

q[5] - "LLOYD" - "KEVIN"

q[6] - "STEVLE" - "DABNEY"

q[7] - "CYNTHIA" - "MALCOLM"

그리고 strLen에는

[7, 5, 6, 5, 7, 6]이 들어가 있겠네요.

다음에 len은 q[현재 사람 이름 길이]군요. 데이터가 n개가 있다고 가정했을 때

평균적으로 n/26만치 들어가므로 (균형적으로 되어있을 때)

시간 복잡도는 O(n^2)쯤 되겠네요.

chogahui05 7년 전 3

백준에서 어느 정도 문제를 푸신 거 같으시니 힌트만 드리겠습니다.

(1) Counting Sort method

카운트 소트가 어떤 식으로 동작했나요?

(2) Sliding Window

현재, 내가 검사하고 있는 사람의 위치를 c라고 표시해 봅시다.

k=3이라고 해 봅시다.

글면

x x x x o o o c o o o x x x x

요런 식으로 표시 가능하겠죠?

여기서 검사하고 있는 사람의 위치를 1칸 뒤로 옮겨봅시다.

글면

x x x x [x] o o o c o o [o] x x x

이래 되겠군요. 여기서 [x]는 제거된 사람이고, [o]는 새로 추가된 사람이지요?

이 경우에 대해서는 어떻게 해야 할까요?

이 문제 풀이가 요 방법만 있는 것도 아니고 관점도 여러 개가 있으니.

곰곰히 잘 생각해 보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 좀 도와주세요

kkw564 7년 전 0

chogahui05 7년 전 1

chogahui05 7년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말