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

0.  문제 링크

 

 

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

2531번: 회전 초밥

---

1.  풀이 방법

 

 

1. 4개씩 투포인터로 범위를 잡는다.
2. set으로 만든 후에, 중복되지 않는 개수를 센다.
3. 만약 행사로 주는 쿠폰에 해당하는 번호가 없으면, 1을 더해서 개수를 센다.
4. 마지막으로 '회전 초밥' 이므로, 맨 뒤에서 맨 앞까지 먹는 경우도 계산해야 한다.

 

• 해당 코드는 매우 느리다. 최적화 작업은 하지 않았다. 통과는 된다.
• 아래는 내가 생각한 더 최적화된 알고리즘이다.

 

1. 4개씩 투포인터로 범위를 잡는다.
2. 초밥을 세기 전에 중복을 먼저 체크한다. 중복을 체크하는 방법은 다른 리스트를 사용하여 계산한다.
3. 하나씩만 포인터를 옮길 것이므로 중간의 3개는 변동되지 않는다. 따라서 맨 앞의 초밥과 맨 뒤의 초밥만 업데이트하고, 중복 체크와 쿠폰 체크를 하면 된다.
4. k + 1이 아마 최댓값일 것이므로, 정답 중에 k + 1이 나오면 그대로 종료한다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline


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

    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

    print(ans)

---

3.  마무리