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)쯤 되겠네요.

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

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

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

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

곰곰히 잘 생각해 보세요.