kkw564   4년 전

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


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

chogahui05   4년 전

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   4년 전

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


(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]는 새로 추가된 사람이지요?

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


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

곰곰히 잘 생각해 보세요.

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