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

---

1. 코드

import sys

n, d, k, c = map(int, sys.stdin.readline().split())
ans = 0
susi = [int(sys.stdin.readline().rstrip()) for _ in range(n)]


for start in range(len(susi)):  #O(30000)
    temp_ans = 0
    temp = []
    end = (start + k) % n

    if start < end:
        temp = susi[start:end]  #O(3000)
    else:
        temp = susi[start:n] + susi[:end]  #O(3000)

    num_set = set(temp)  #O(3000)
    if c not in num_set:  #O(1)
        temp_ans = len(num_set) + 1
    else:
        temp_ans = len(num_set)
    ans = max(ans, temp_ans)
print(ans)

O(NM)으로 알고리즘을 설계해도 풀린다.
O(30000) * O(3000) = O(90,000,000)

동일한 문제이지만 시간복잡도를 고려한
https://www.acmicpc.net/problem/15961 문제를 풀어보자

• REFERENCE
  https://www.secmem.org/blog/2021/01/22/time-complexity/