[15961] 회전 초밥 in python

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

15961번: 회전 초밥

> 투 포인터

> 슬라이싱 윈도우

 

윽..

이 문제 간단해보였는데

전혀 아니었다!

 

혽자선 도저히 못 풀 것 같아서

결국 고수님들의 풀이를 살펴보았다.

 

그래도 이해가 되지 않아서

계속 그림을 그려가며 

이해하기 위해 노력했다.

 

일단 코드는 아래와 같다.

어떤 코드에서는 딕셔너리를 이용하라고 하는데

나는 cache라는 리스트를 이용하였음.

 

n, d, k, c = map(int, input().split())
array = list((int(input()) for _ in range(n)))
answer = 0
cache = [0] * (d + 1)
for i in array[:k]:
    if not cache[i]:
        answer += 1
    cache[i] += 1
cnt = answer
print(cache)

for i in range(n):
    if answer <= cnt:  # answer값 업데이트
        if cache[c]:
            answer = cnt
        else:
            answer = cnt + 1
    left = array[i]
    right = array[(i + k) % n]
    cache[left] -= 1 # 방문체크
    if not cache[left]: # 현재 리스트에 left 위치에 있는 값이 없는경우
        cnt -= 1
    if not cache[right]: # 현재 리스트에 right 위치에 있는 값이 없으면
        cnt += 1 # 현재 리스트에 값 추가하는거니까 +1
    cache[right] += 1 # 방문체크

print(answer)

 

일단 문제에서 주어진 예시로 설명을 풀어나가 보겠음.

n=8 #초밥 벨트에 놓인 접시의 수

d=30, # 초밥의 가짓수

k=4, # 연속해서 먹는 접시의 수

c=30, # 쿠폰 번호

초밥의 종류 array = [7,9,7,30,2,7,9,25]

 

answer -> 최종값 (초밥 가짓수의 최댓값)

cnt ->  탐색하면서 계산되는 초밥 가짓수

cache -> 방문횟수를 저장하는 리스트 (자세한 설명은 아래에서)

 

temp -> 연속해서 먹는 접시를 담아둔 리스트

temp는 코드에는 작성되어 있지 않지만,

설명을 위해 필요한 존재라서 언급함.

 

---

1. 초기 과정이 필요하다. 

기준값이 있어야 계산을 할 수 있기 때문.

 

array[:k] 범위에서 For문을 돌린다.

(1) temp 리스트에 담겨있는 수가 아니면 ?

temp에 담아준다. (-> 이 과정이 answer + 1)

 

(2) 만약 이미 temp 리스트 안에 똑같은 초밥 접시가 들어있다면?

담을 필요가 없음. (따라서 answer 값은 그대로 유지)

왜냐하면 우리는 지금 초밥 가짓수를 최대로 끌어올려야 하기 때문에

중복돼서 좋을 게 없기 때문이다.

하지만, cache 리스트에는 체크를 해줘야 함

아래와 같은 이유 때문.

 

(3) 인덱스가 꼬임을 방지하기 위해

중복되었던 안 되었던 방문 처리는 해줘야 함.

즉 cache 리스트는

현재 연속해서 먹는 접시의 리스트에

어떤 초밥이 담겨있는지 확인하는 리스트라고 보면 될 듯 하다.

(방문 처리와 비슷한 개념)

 

---

2. for문 (n번, 즉 초밥 벨트에 놓인 접시의 수만큼)

(1) answer 값 업데이트

answer값보다 cnt의 값이 커지거나 같은 경우 >>

if 현재 연속해서 먹는 접시의 리스트(temp)에 쿠폰번호 초밥이 들어가있는 경우:

-> answer = cnt

else:

-> answer = cnt+1 (쿠폰 번호 초밥을 temp 리스트에 넣어준다)

 

(2) left 값

left는 array[i]번째에 위치해있는 초밥의 번호

 

(3) right 값 

right는 array[(i+k)%n]

-> array를 연속해서 붙이지 않고 그냥 쓰려면

% 연산자를 이용해서 순환을 할 수 있음.

 

만약 i가 7이고, k가 4, array의 길이는 8

i+k = 7+4 = 11이니까 array의 길이를 넘어서 

이대로 쓰면 인덱스 에러가 난다.

처음에 array.extend(array)를 해줬더라면

인덱스 에러가 나지 않겠지만,

위 코드에서는 위 과정을 해주지 않았기 때문에

% 연산자가 필요하다.

 

11 % 8 = 3, 

즉 위 예시에서는 right의 값이 array[3]이 된다.

 

* 순환 문제풀 때 % 연산자

혹은 extend를 통해 배열을 이어붙이는 생각을 떠올리자 *

 

(4) 연속해서 먹는 접시의 리스트 범위를 오른쪽으로 한 칸 이동

[7,9,7,30]이었으면

[9,7,30,2]로 

오른쪽으로 한 칸 이동하는 과정

 

left +1 을 해줘야함.

그래서 cache[left]-=1을 해줌.

왜냐면 오른쪽으로 이동하게 되면

7은 더이상 해당 리스트 범위에 존재하지 않게 되니까.

 

그리고 나서 cache[left]의 값이 0이라면? temp리스트에 들어있지 않다면?

cnt-=1 # temp리스트의 길이가 1 줄어든다.

반대로 1 이상이라면? 

연속해서 먹는 접시의 리스트 범위 내에 left 값이 들어있는 것이기 때문에

아무런 작업을 할 필요가 없음.

 

 

마찬가지로 cache[right]의 값이 0이라면? temp 리스트에 들어있지 않다면?

cnt+=1 # temp 리스트의 길이가 1 늘어난다. 

 

cache[right]+=1 > 이거는 중복되든 아니든 인덱스 꼬임 방지를 위해

꼭 해줘야하는 과정이다!

 

 

 

 

---