308. 회전 초밥

백준

1. 투포인터

최적화

import sys
from collections import Counter
input = sys.stdin.readline

# 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값

n, d, k, c = map(int, input().split())
rail = [int(input()) for _ in range(n)]
count = Counter()
left = 0
right = 0
cnt = 0
kind = 0
answer = 0
while left < n - 1:
    if cnt >= k: #k개 이상이면 좌측 이동
        count[rail[left]] -= 1
        if count[rail[left]] == 0:
            kind -= 1
        left = (left + 1) % n
        cnt -= 1
    else: 
        if count[rail[right]] == 0:
            kind += 1
        count[rail[right]] += 1
        right = (right + 1) % n
        cnt += 1
    if kind >= answer:
        answer = kind
        if count[c] == 0:
            answer += 1

print(answer)

풀이

import sys
from collections import defaultdict
input = sys.stdin.readline

#주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값

n, d, k, c = map(int, input().split())
rail = [int(input()) for _ in range(n)]

result, right = 0, 0

for left in range(n):
    while right - left < k:
        right += 1

    keep = set()
    for i in range(left, right):
        i %= n #회전 고려
        keep.add(rail[i])

    cnt = len(keep)
    if c not in keep:
        cnt += 1
    result = max(result, cnt)


print(result)

2. C++

#include <bits/stdc++.h>
using namespace std;

int n, d, k, c;
vector<int> rail;
map<int, int> m;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> d >> k >> c;
	for (int i = 0,t; i < n; i++) {
		cin >> t; rail.push_back(t);
		if (m.find(t) == m.end()) m.insert(make_pair(t, 0));
	}
	if (m.find(c) == m.end()) m.insert(make_pair(c, 0));

	int left = 0, right = 0, cnt = 0, kind = 0, answer = 0;
	while (left != n - 1) {
		if (cnt >= k) {
			if (--m[rail[left]] == 0)
				kind--;
			left = (left + 1) % n;
			cnt--;
		}
		else {
			if (m[rail[right]]++ == 0)
				kind++;
			right = (right + 1) % n;
			cnt++;
		}
		if (kind >= answer) {
			answer = kind;
			if (m[c] == 0)answer++;
		}
	}
    cout << answer;
	return 0;
}