๋ฌธ์
https://www.acmicpc.net/problem/2531
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x14๊ฐ - ํฌ ํฌ์ธํฐ
์๊ณ ๋ฆฌ์ฆ: ํฌ ํฌ์ธํฐ, ๋ธ๋ฃจํธํฌ์ค, ์ฌ๋ผ์ด๋ฉ ์๋์ฐ
ํ์ด

๋ฌธ์ ์ ์กฐ๊ฑด์ ์ ๋ฆฌํด๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
- ์ต๋ํ ๋ง์ ์ข ๋ฅ์ ์ด๋ฐฅ์ ๋จน์ด์ผ ํจ
- ๋จน์ ์ ์๋ ์ด๋ฐฅ์ ๊ฐฏ์๋ k๊ฐ
- ์ฟ ํฐ์ k๊ฐ์ ์ด๋ฐฅ๊ณผ๋ ๋ณ๊ฐ๋ก ์ฌ์ฉํ ์ ์์
๋ง์ง๋ง ์กฐ๊ฑด ๋๋ฌธ์ ์ด์ง ํท๊ฐ๋ ธ์๋ค.
๋ฒจํธ ์์ ์ฐ์๋ k๊ฐ์ ์ด๋ฐฅ๊ณผ ์ฟ ํฐ์ด๋ฐฅ์ด ๋ถ์ด์์ด์ผ ํ๋ ์ค ์์๋๋ฐ ์๋์๋ค.
๐ฆ์ฟ ๐ฆ๐ฆ์ด1 ์ด2 ์ด3๐ฆ๐ฆ ← ์ด๋ฐ์์ผ๋ก ์ ํํด๋ ์๊ด์์
๊ทธ๋ฅ ์ฟ ํฐ์ด๋ฐฅ์ ์ ์ธํ๊ณ ์ ํํ ์ ์๊ฐ k๊ฐ์ด๊ธฐ๋ง ํ๋ฉด ๋๋๊ฒ์ด๋ค.
๋ํ ์ํ์ผ๋ก ๋์๊ฐ๋ ๋ฒจํธ ์์ ๋์ฌ์๋ "ํ์ " ์ด๋ฐฅ์์ ์ ์ํด์ผํ๋ค.
๋ฐ๋ผ์ ์ฃผ์ด์ง ์ด๋ฐฅ ๋์ด์ ๋ฆฌ์คํธ๋ก ์ ์ฅ ํ [:k]๋งํผ์ ๋ค์ ์ถ๊ฐํด์ค ๋ค ์งํํ๋ค. (์ ํํ ๊ณ์ฐํ๋ฉด [:k-1])
dish = [int(input()) for _ in range(N)]
dish.extend(dish[:k]) # ํ์ ์ด๋ฐฅ์ด๋ฏ๋ก ์ํํ์ ๊ณ ๋ ค
์ด์ ํฌํฌ์ธํฐ๋ก ํ์์ ์งํํ๋ค.
left๋ 0์ผ๋ก ์ค์ , right์ 0๋ถํฐ N + k๊น์ง ๋๋ ค๋๊ฐ๋ฉด์ ์กฐ๊ฑด์ ์ฒดํฌํ๋ค.
๋์ ๋ฐ๋ผ ๊ฐ ํฌ์ธํฐ๊ฐ ์์นํ ์ด๋ฐฅ์ ์ข
๋ฅ, ๊ทธ ์ด๋ฐฅ์ ๊ฐฏ์๋ฅผ ํ์ธํด์ผ ํ๋ฏ๋ก ๋์
๋๋ฆฌ๊ฐ ํ์ํ๋ค.
๊ทธ๋ฆฌ๊ณ ํ์ฌ ์ ํํ ์ด๋ฐฅ๋ค์ ์ข
๋ฅ ์๋ ๋ณ์cnt์ ๋ฐ๋ก ์ ์ฅํ๋ค.
- ์ด๋ฐฅ์ ํ๋์ฉ ๋ด๊ณ ๋์ ๋๋ฆฌ์ ํด๋น ์ด๋ฐฅ์ ๊ฐฏ์๋ฅผ ์ถ๊ฐํ๋ค.
- ๋จน์ด๋ณด์ง ์์ ์ด๋ฐฅ์ด๋ผ๋ฉด
cnt + 1 - k๊ทธ๋ฆ์ ์ด๊ณผํ์๊ฒฝ์ฐ => left ํฌ์ธํฐ ์ฒดํฌ
- ๋ง์ฝ left ์ด๋ฐฅ์ ๊ฐฏ์๊ฐ 1 ์ด๋ผ๋ฉด
cnt - 1 - left ์ด๋ฐฅ์ ๊ฐฏ์๋ฅผ -1 ํด์ฃผ๊ณ left ํฌ์ธํฐ ํ ์นธ ์ด๋
- ๋ง์ฝ left ์ด๋ฐฅ์ ๊ฐฏ์๊ฐ 1 ์ด๋ผ๋ฉด
- ๊ธฐ์กด ์ต๋๊ฐ๊ณผ ํ์ฌ ๊ฐ์ ๋น๊ต
cnt+ (์ฟ ํฐ์ด๋ฐฅ์ด k๊ฐ์ ํฌํจ๋์ด์๋ค๋ฉด 0, ์๋๋ผ๋ฉด 1)
์ ์ฒด ์ฝ๋
# ์ฟ ํฐ์ด๋ฐฅ์ k๊ฐ์ ์ ์์๋ ๋ณ๊ฐ๋ก ์ฌ์ฉํ ์ ์์.
# ๋ฉ๋ชจ๋ฆฌ: 33432KB / ์๊ฐ: 72ms
from sys import stdin
input = stdin.readline
# N: ์ ์ ์, d: ์ด๋ฐฅ์ ๊ฐ์ง์, k: ์ฐ์ํด์ ๋จน๋ ์ ์ ์, c: ์ฟ ํฐ๋ฒํธ
N, d, k, c = map(int, input().split())
dish = [int(input()) for _ in range(N)]
dish.extend(dish[:k]) # ํ์ ์ด๋ฐฅ์ด๋ฏ๋ก ์ํํ์ ๊ณ ๋ ค
sushi = {}
left = 0
ret = cnt = 0 # ret: ์ต๋๊ฐ, cnt: ํ์ฌ ๋จน์ ์ด๋ฐฅ์ ์ข
๋ฅ ๊ฐฏ์
for right in range(len(dish)):
sushi[dish[right]] = sushi.get(dish[right], 0) + 1
if sushi[dish[right]] == 1: # ๋จน์ด๋ณด์ง ์์ ์ข
๋ฅ๋ผ๋ฉด ์นด์ดํธ
cnt += 1
# k๊ทธ๋ฆ์ ์ด๊ณผํ์๊ฒฝ์ฐ
if (right-left+1) > k:
if sushi[dish[left]] == 1: # ๋ง์ฝ ํ๋๋ฟ์ธ ์ค์์๋ค๋ฉด ์นด์ดํธ๋ฅผ ๊ฐํด์ค
cnt -= 1
sushi[dish[left]] -= 1
left += 1
# ๋จน์ ์ด๋ฐฅ์ ์ข
๋ฅ + ์ฟ ํฐ์ด๋ฐฅ์ด ํฌํจ๋์ด์๋ค๋ฉด 0, ์๋๋ผ๋ฉด 1
curr = cnt + (1 if sushi.get(c, 0) == 0 else 0)
ret = max(ret, curr)
print(ret)
์ธ์์ ํ์ ์ด๋ฐฅ.
๊ทธ๋์ ๋ ํฌํฌ์ธํฐ+๋์ ๋๋ฆฌ ์กฐํฉ ๋ฌธ์ ๊ฐ ๊ฝค ๋ง์๊ฒ๊ฐ๋ค.
๊ธฐ๋ณธ์ ์ธ ํฌํฌ์ธํฐ ๋ฌธ์ ๋ ์ด๋ถํ์์ ๋ง์ด ๋ถํฌ๋์ด์์ผ๋ ๋ฒ๊ฐ์๊ฐ๋ฉฐ ํ๋ฉด ์ข์๋ฏ์ถ๋ค~