[ 백준 / Python ] #2531 회전초밥

문제

 

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

2531번: 회전 초밥

---

Algorithm

k개의 구간안에 있는 초밥들과 쿠폰으로 받을 수 있는 초밥중 서로 다른 초밥 개수의 최댓값을 구하는 문제이다. 구간을 정해주기 위해 투포인터를 사용하였다. 

서로 다른 초밥의 개수를 구하기 위해 딕셔너리를 사용하였다. 회전초밥이므로 확인해야 하는 구간은 총 n개이고, 예제 입력1에서 25,7,9,7을 고르는 경우도 있으므로 초밥종류를 가지고 있는 배열 arr에 k-1개만큼만 더 뒤에 추가해준다.

이제 while문을 돌려서 최댓값을 찾아주면 된다. 반복문의 처음에는 구간 사이의 값을 딕셔너리에 넣어주기 위해 s==0일때 초기 셋팅을 해준다. 반복문을 돌리는 과정에서 s+=1 , e+=1이 되는데, 딕셔너리에 현재 s-1값이 존재하고 e값이 존재하지 않으므로 추가하는 작업을 해준다. 만약에 추가하는 과정에서 딕셔너리에 있으면 +=1을 해주고, 아니면 새로 만들어 준다.

이제 현재 구간의 서로다른 초밥의 개수를 찾아주면된다. 딕셔너리에 추가하는 작업을 할떄 같은 종류가 들어올때 key를 추가 하지 않았으므로 len함수로 구해주면 된다. 만약에 쿠폰으로 얻을 수 있는 종류가 딕셔너리에 있으면 그대로, 아니면 +1을 해준후에 최댓값 갱신을 해주면 된다. 

---

 

 

Code

input = __import__('sys').stdin.readline

n,d,k,c = map(int,input().split())
arr = []
for i in range(n):
    arr.append(int(input()))

for i in range(k-1): 	# 구간 시작하는 포인터가 n-1일때 index를 채워주기위해 arr뒤에 k-1개만큼 추가함
    arr.append(arr[i])

s = 0 			# 구간 시작 포인터
e = k-1 		# 구간 끝 포인터
temp = 0 		# 현재 구간에서의 서로 다른 초밥의 개수
dict = {} 		# 서로 다른 초밥의 개수를 판별하기 위한 딕셔너리
maxs = 0 		# 최댓값

while s < n:
    if s == 0:
        for i in range(k):
            if arr[i] in dict:
                dict[arr[i]] += 1
            else:
                dict[arr[i]] = 1
    else:
        if dict[arr[s-1]] == 1:
            del dict[arr[s-1]]
        else:
            dict[arr[s-1]] -= 1

        if arr[e] in dict:
            dict[arr[e]] += 1
        else:
            dict[arr[e]] = 1

    if c in dict:
        temp = len(dict)
    else:
        temp = len(dict)+1

    maxs = max(maxs,temp)
    s+=1
    e+=1

print(maxs)