[백준 - Python] 15961 - 회전 초밥

0.  문제 링크

 
 

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

15961번: 회전 초밥

2023.05.15 - [Computer Science/알고리즘] - [백준 - Python] 2531 - 회전 초밥

[백준 - Python] 2531 - 회전 초밥

---

1.  풀이 방법

 
 

• optimize 코드가 최적화 한 코드다.
• 앞선 글인 2531 백준과 비교해서 해당 문제는 테케가 아주 커진 것 같고, 시간 조건에 제약이 더 생긴 것 같다.
• 앞선 글의 2531 코드를 그대로 넣으면 시간 초과가 발생한다.
• 따라서 최적화 작업을 반드시 해야 한다.

 

1. 우선 초깃값을 설정한다. 왜냐하면 해당 초깃값을 설정함으로써 1부터 left를 시작하여 끝까지 가기 때문이다. 또한 초기에 정한 init 값을 기준으로 +1, -1이 된다. 따라서 초깃값 설정은 필수다.
2. sliding window 방식을 사용하여 빠진 값, 새로 들어온 값들을 체크한다.
3. 이때 체크하는 방식은 해당 window 내에서 특정 값이 몇 개 들어가 있는지 체크하는 것이다.
4. 빠진 값을 뺐는데, 체크 값에서 해당 위치가 0이라면 윈도우 내에는 중복 값이 없는 것이므로, cnt -= 1을 하면 된다.
5. 새로 추가한 값을 넣었는데, 체크 값이 해당 위치에서 1이라면 윈도우 내에서 중복 값이 없는 것이므로, cnt += 1을 하면 된다.
6. 최종적으로 쿠폰 번호가 해당 윈도우 안에 있다면, else 문을 통하여 최댓값을 갱신하고, 해당 윈도우 안에 없다면 if 문을 통하여 최댓값을 갱신한다.
7. 참고로 정답 중에 k + 1이 나오면 그대로 반환한다.

---

2.  코드

 
 

import sys
input = sys.stdin.readline


def slow():
    left = 0
    right = left + k
    ans = 0

    while right <= n:
        temp = set(maps[left: right])
        if c in temp:
            ans = max(ans, len(temp))
        else:
            ans = max(ans, len(temp) + 1)

        left += 1
        right += 1

    right = 1

    while left < n:
        temp = set(maps[left: n] + maps[0: right])
        if c in temp:
            ans = max(ans, len(temp))
        else:
            ans = max(ans, len(temp) + 1)

        left += 1
        right += 1

    return ans


def optimize():
    check = [0] * (d + 1)
    init = 0

    for i in range(0, k):
        num = maps[i]
        if check[num] == 0:
            init += 1
        check[num] += 1

    ans = init
    cnt = init

    for left in range(1, n):
        right = (left + k - 1) % n

        bef = maps[left - 1]
        aft = maps[right]

        check[bef] -= 1
        if check[bef] == 0:
            cnt -= 1

        check[aft] += 1
        if check[aft] == 1:
            cnt += 1

        if check[c] == 0:
            ans = max(ans, cnt + 1)
        else:
            ans = max(ans, cnt)

        if ans == k + 1:
            return ans

    return ans


if __name__ == "__main__":
    n, d, k, c = map(int, input().split())
    maps = [int(input()) for _ in range(n)]

    # print(slow())
    print(optimize())

---

3.  마무리

 
 

참고로 최적화된 코드와 그냥 Brute Force 방식을 사용한 코드는 약 50배의 시간 차이가 난다.