백준_15961_회전 초밥(python)

※ 접근

 입력 개수가 최대 3,000,000만이었기 때문에 반복을 한 번 돌아야겠다고 생각을 했고 이벤트에 무조건 참여해야했기에 k개의 초밥을 무조건 먹었어야했다. 그래서 k개씩 짤라서 이동해야했기에 슬라이딩 윈도우를 사용했다. (문제에서 주어진 조건대로 구현했지만 이런 방식의 알고리즘을 슬라이딩 윈도우라고 부른다.)

 

※ 풀이

1. 이벤트에 무조건 참여해야했기에 c 쿠폰번호의 초밥은 무조건 먹었다고 가정했다.

2. 처음에는 left, right(코드에서는 left, right가 없지만)가 움직일 필요가 없기에 k개까지 초밥을 먹는다.

3. 그 다음부터는 가장 맨 처음 먹었던 초밥은 뱉고 마지막에 먹었던 초밥 바로 오른쪽 것을 먹어주는 동작을 반복한다.

 

-- 정답 코드 --

import sys
input = sys.stdin.readline

n,d,k,c = map(int,input().split())
count = 1
s = [0] * (d+1)
s[c] = 1
data = []
for i in range(n):
    data.append(int(input()))

for i in range(k):
    s[data[i]] += 1
    if s[data[i]] == 1:
        count += 1

answer = count

for i in range(n-1):
    s[data[i]] -= 1
    if s[data[i]] == 0:
        count -= 1
    s[data[(i+k) % n]] += 1
    if s[data[(i+k) % n]] == 1:
        count += 1
    answer = max(answer, count)

print(answer)

 

 

 

-- 틀린 코드--

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

n,d,k,c = map(int,input().split()) # 입력
answer = 0 #answer 마지막에 정답으로 출력할 변수 0으로 초기화
data = [] # 리스트 선언
s = set() # 집합 선언
left, right = 0,k-1 # 투 포인터
dic = defaultdict(int) # defaultdict라고 해당 key값이 없으면 스스로 해당 키를 만들어줌
count = 0
for i in range(n): # n번 동안 반복한다.
    number = int(input()) # 초밥 번호를 입력받는다.
    data.append(number) # 리스트에 추가한다.

for i in range(n):
    count += 1
    s.add(data[i])
    dic[data[i]] += 1
    if count < k: # k가 되기전까지는 저 행동을 반복     
        continue 
    elif count == k: # k와 처음 같아질때는 left와 right의 위치를 옮기는 행동을 안해도되니까
        if c not in s: # 쿠폰번호가 집합에 있었는지 없었는지
            answer = max(answer, len(s) + 1)
        else:
            answer = max(answer, len(s))
    else:
        dic[data[left]] -= 1 #일단 하나를 없애야지
        if dic[data[left]] == 0: # 0과 같아졌다면
            s.remove(data[left]) # 처음꺼는 없애고
        left += 1 # 처음꺼 인덱스도 한 칸 옆으로 옮겨준다.
        right = (right + 1) % n
        dic[data[right]] += 1
        s.add(data[right]) # 마지막꺼를 추가해준다. (집합형이라 없으면 추가되고 있어도 상관없음)
        if c not in s:
            answer = max(answer, len(s) + 1)
        else:
            answer = max(answer, len(s))
        
print(answer)

 

- 틀린 코드를 기재했는데 맞왜틀이란 것은 없다고 생각하지만 틀린 이유를 모르겠다. 주변에 알고리즘을 잘하는 지인에게 물어봤는데 본인도 왜 틀렸는지 모르겠다고 한다. 

 

※ 회고 

할 수 있다!!