[백준] 회전초밥 / Python 실1

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

처음에 했던 생각

 

for문으로 n개의 초밥을 탐색하면서

i번째 초밥부터 k개의 초밥을 set으로 묶어서 종류를 헤아린 후

종류 안에 c 쿠폰 초밥이 포함되지 않으면 1을 더해준 후

이전 i-1번째 초밥까지 헤아린 종류 수 중 최댓값을 변수에 저장해놓고

현재 상태에서 max로 비교해서 업데이트하면 어떨까

 

= 시간초과 엔딩

 

<시간초과>

#접시, 초밥가짓수, 연속, 쿠폰번호
n,d,k,c = map(int,input().split())

a = [int(input()) for _ in range(n)]

#쿠폰번호가 포함되지 않은 k개를 먹으면 최대가짓수?

dp = [0]*n

#i번째 위치에서 k개를 먹을 때 가짓수?
s=0
for i in range(n):
    temp=[]
    t=0
    for j in range(i,i+k):
        temp.append(a[j%n])
    t = len(set(temp))

    if c not in temp:
        t+=1
    s = max(s,t)
    
print(s)

 

그렇다면 o(n)으로 해결해야 하는군아...

 

다른 블로그를 참고해서 아이디어를 얻엇다

참고로 c++로 구현된 코드들 파이썬으로 옮겨서 테스트해봤는데 다 시간초과 뜸

파이썬은 엄격하구나...

 

for문을 돌면서

 

i번째 요소에서 i+k번째 요소까지 탐색해서 초밥을 k개 주워먹을 때

만약 i+k번째가 n 이내라면 그대로 초밥 배열을 a[i:i+k]로 잘라서 set을 씌워서 종류를 구해도 되지만

i+k번째가 n을 벗어나면 두 파트로 나눠야 됨

i번째부터 끝까지 자른 배열을 set으로 씌우고

처음부터 (i+k)%n 번째까지 자른 배열을 set에 업데이트 해줘야 함

 

(i+k)를 n으로 나눈 나머지를 구하면 i부터 끝까지 자른 배열에서 부족한 원소를 채워서 k개를 탐색할 수 있음

 

그리고 set에 c를 추가하면, 원소가 이미 있는 경우는 무시될거고, 없으면 추가될거임

이게 아이디어 포인트라고 생각햇다

나는 if c in temp이런거나 생각했는데;;

 

s값을 이전 i-1번째까지 요소에서 구했던 값이랑 현재 i번째 요소에서 구한 초밥종류수랑 비교해서 max로 업뎃한다

 

그리고 s를 출력하면 끝

 

아이디어란...

 

#접시, 초밥가짓수, 연속, 쿠폰번호
n,d,k,c = map(int,input().split())

a = [int(input()) for _ in range(n)]

#쿠폰번호가 포함되지 않은 k개를 먹으면 최대가짓수?

dp = [0]*n

#i번째 위치에서 k개를 먹을 때 가짓수?
s=0
for i in range(n):
    if i<=n-k:
        temp = set(a[i:i+k])
    else:
        temp = set(a[i:])
        temp.update(a[:(i+k)%n])
    temp.add(c)
    s = max(s,len(temp))

    
print(s)