그냥 코딩하는 사람의 블로그

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

풀이 과정

1. 사전순으로 정렬된 리스트를 얻어야 하므로, Recursion으로 구현 할 때 현재 합에서 1->2->3 순으로 더하도록 Recursion을 진행한다.
2. Recursion을 진행한다.
   • 현재 사용한 숫자들에 1, 2, 3을 넣고, 사용한 숫자를 합계에 더해서 다음 Recursion 호출
   • Recursion을 진행하다 현재 합계가 n보다 커진다면 종료
   • n과 같다면 리스트에 추가하고 종료한다.
3. 2번 과정을 진행하면 결국 1,2,3의 합으로 나타내는 모든 방법이 정렬되어 있는 리스트를 얻게 된다.
   • 따라서, k-1번째 인덱스의 방법을 출력해주면 된다.
   • 이 때, k-1이 방법의 수보다 큰 경우가 있으므로, 이 때는 -1을 출력해준다.

소스 코드

n, k = map(int, input().split())

case = []
def dfs(numbers, sumation, target):
    global case

    if sumation == target:
        case.append(numbers)
        return
    if sumation > target:
        return

    for i in [1, 2, 3]:
        dfs(numbers + [i], sumation + i, target)

dfs([], 0, n)
if k - 1 < len(case):
    print("+".join(map(str, case[k-1])))
else:
    print(-1)

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이 과정

• 이렇게 2+1+1이랑 1+1+2, 1+2+1을 모두 같은 것으로 처리하기 위해서는 한 점(dp[i])에서 dp[i]-1, dp[i]-2, dp[i]-3일때를 한번에 더해서는 겹치는 수가 생겨서 안된다.

• 정수 1,2,3을 기준으로, 맨 마지막에 1이 나왔을 때를 계산하고, 맨 마지막에 2가 나왔을 때를 계산하고, 3이 나왔을 때를 계산해주는 방식으로 테이블을 채운다.

• 따라서,

  • 1일때는 dp[i] = dp[i] + dp[i-1],
  • 2일때는 dp[i] = dp[i] + dp[i-2],
  • 3일때는 dp[i] = dp[i] + dp[i-3]

소스 코드

total = int(input())
for _ in range(total):
    T = int(input())
    dp = [1] + [0] * T
    for i in [1, 2, 3]:
        for j in range(1, T+1):
            if j - i >= 0:
                dp[j] += dp[j-i]
    print(dp[T])

문제 설명

문제

심마니 영재는 산삼을 찾아다닌다.

산삼을 찾던 영재는N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.

마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.

점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.

각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.

매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.

에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.

영재는 첫 번째 돌에서부터 출발한다.

입력

첫 번째 줄에는 돌의 개수N이 주어진다.

N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.

마지막 줄에는K가 주어진다.

출력

산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.

제한

• 1 ≤ N ≤ 20
• 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.

풀이 과정

• 2차원 DP 테이블을 구성한다.

  • DP[i][0] : i번째 돌까지의 최소비용, 매우 큰 점프 사용하지 않음.
  • DP[i][1] : i번째 돌까지의 최소비용, 매우 큰 점프 사용

• 현재 위치가 x라고 둘 때, 갈수있는 모든 돌의 비용들을 갱신한다.

  • 점프(+1)하는 경우, 큰점프(+2) 하는 경우, 매우 큰 점프(+3) 하는 경우
  • 매우 큰 점프의 경우, DP[x][1]일때는 이미 점프한 경우이므로 점프할수 없으므로, DP[x][0]에 대해서만 고려한다.

• 마지막으로, DP[N]의 최솟값을 출력해주면 된다.

  • 매우 큰점프를 사용하였거나, 사용하지 않았을 때중 최솟값

소스 코드

import sys
from collections import deque

N = int(input().rstrip())

small = [0] * (N+1)
big = [0] * (N+1)

for i in range(1, N):
    a, b = map(int, input().rstrip().split())
    small[i], big[i] = a, b

K = int(input().rstrip())

INT_MAX = int(10e9)
dp = [[INT_MAX] * 2 for _ in range(N+1)]
dp[1][0], dp[1][1] = 0, INT_MAX
for i in range(1, N):
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+small[i])
    dp[i+1][1] = min(dp[i+1][1], dp[i][1]+small[i])
    if i + 2 <= N:
        dp[i+2][0] = min(dp[i+2][0], dp[i][0]+big[i])
        dp[i+2][1] = min(dp[i+2][1], dp[i][1]+big[i])
    if i + 3 <= N:
        dp[i+3][1] = min(dp[i+3][1], dp[i][0] + K)


print(min(dp[N]))

문제 설명

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

풀이 과정

1. [1~9]까지의 값을 미리 큐에 넣어둔 다음 BFS를 진행한다.
   • N = 0일때는 따로 예외로 처리해주어야 함.
   • 현재 값을 N이라고 할 때, N의 맨 마지막 자리 숫자보다 작은 숫자들을 뒤에 붙여서 큐에 다시 넣어준다.
   • 예시로 N이 2라고 할때, 20, 21을 큐에 넣어준다.
2. BFS를 진행하면서 큐가 비게 되면 N번째 감소하는 수는 만들 수 없는 것이므로 -1 리턴
   • 큐에서 뺀 수가 N번째 숫자면 해당 수 리턴

소스 코드

import sys
from collections import deque

N = int(input().rstrip())

def bfs(N):
    queue = deque([i for i in range(1, 10)])
    count = 0

    while queue:
        t1 = queue.popleft()
        count += 1
        if count == N:
            return t1
        dest = int(str(t1)[-1])
        for i in range(dest):
            queue.append(int(str(t1) + str(i)))

    return -1

if N == 0:
    print(0)
else:
    print(bfs(N))

문제 설명

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 [i][j]형태로 주어진다. [i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, [i][j] 는 [j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. [i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 [i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

풀이 과정

• DFS로 풀수도 있을거라고 생각하지만, 도시의 개수가 최대 10개로 매우 작으므로 전체 경우의 수를 조합으로 구해서 해결

1. 각 도시들을 번호를 붙임
   • N개의 도시라고 하면, [0, 1, 2, ... , n-1]까지 번호 붙임
   • [i][j]를 i에서 j도시로 이동할 때 비용이라고 둔다.
2. 번호들로 조합을 구성한다.
   • itertools.permutations 사용
   • 이후, 시작도시로 돌아와야 하므로 각각의 케이스의 맨 뒤에 맨 첫번째 도시 번호를 붙여준다.
3. 각각의 케이스에 대해 비용이 얼마나 나오는지 계산
   • 진행하다가 [i][j]가 0이 되는 경우는 길이 없는것이므로 중지
4. 비용의 최솟값을 출력해준다.

소스 코드

import sys
from itertools import permutations

input = sys.stdin.readline
N = int(input().rstrip())
W = [list(map(int, input().rstrip().split())) for _ in range(N)]

total_case = list(permutations([i for i in range(N)], N))

def check_case(W, case):
    case = case + (case[0], )
    cost = 0
    for i in range(1, len(case)):
        if W[case[i]][case[i-1]] == 0:
            return int(10e9)
        cost += W[case[i]][case[i-1]]

    return cost

answer = int(10e9)
for case in total_case:
    answer = min(answer, check_case(W, case))

print(answer)

문제 설명

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력 한다.

풀이 과정

• 이전에 푼 문제중에 다음 순열이라는 문제가 있는데, 해당 문제와 거의 유사하나 몇몇 부분을 바꾸어주어야 하는 부분이 있음.

1. 순열을 오른쪽에서 왼쪽으로 진행하면서 array[i-1]>array[i]인 구간을 찾는다.
   • 이 때, 이러한 구간이 없으면 제일 첫번째 순열인 것이므로 -1을 출력해주면 된다.
   • 구간이 있다면, i-1이 바뀌게 될 요소의 인덱스이다.
2. 다음으로, array[i-1]보다 작은 요소의 인덱스를 오른쪽에서 왼쪽으로 진행하면서 찾는다.
   • 이 요소의 위치를 j라고 두자.
3. array[i-1], array[j]를 서로 바꾸어 준다.
4. 이후, i 이후의 배열들을 뒤집어준다.
   • 내림차순으로 정렬해야 하는데, (1)에서 i를 찾을때, i 이후는 모두 오름차순임을 알 수 있다.
   • 따라서 뒤집어 주면 i 이후는 모두 내림차순이 된다.
5. 배열을 출력해주면 끝

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())

sequence = list(map(int, sys.stdin.readline().rstrip().split()))

def prev_permutation(sequence):
    i = len(sequence) - 1

    # sequence[i-1] > sequence[i]인 부분을 찾음 => i-1이 바꿔지게 될 위치임.
    while i > 0 and sequence[i-1] < sequence[i]:
        i = i - 1

    if i == 0:
        return None

    swap_pos = i-1
    j = len(sequence) - 1
    # 오른쪽에서 시작했을 때, 바꿔지게 될 요소보다 작은 수들중 처음 나오는 요소가
    # 바뀌어지게 된다.
    while j > 0 and sequence[swap_pos] <= sequence[j]:
        j = j - 1

    sequence[swap_pos], sequence[j] = sequence[j], sequence[swap_pos]

    # 바뀌는 점 이후는 내림차순이 되어야 함
    # 위 while문을 보면 알겠지만.. 바뀌는 위치 기준으로 오른쪽은 오름차순이 되어 있음.
    # 따라서, 그냥 뒤집어주면 된다.
    sequence = sequence[:i] + sequence[i:][::-1] 
    return sequence


p = prev_permutation(sequence)
if p == None:
    print(-1)
else:
    print(*p)

문제 설명

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

풀이 과정

1. 처음에 생각했을 때는, 최댓값, 최솟값, 두번째 최댓값, ... 이런식으로 배열해야 되는줄 알았으나.. 그냥 틀리길래 입력의 크기를 보니 최대 8개이므로 전수조사 하면 된다.
2. 파이썬에서 제공하는 itertools.permutations 함수 사용
   • permutations(list, 갯수) => list에서 갯수만큼 뽑아서 조합
3. 각각의 조합들에 대해 식의 값을 구한 후, 최댓값을 출력해주면 된다.

소스 코드

import sys
from itertools import permutations

input = sys.stdin.readline
N = int(input().rstrip())
array = list(map(int, input().rstrip().split()))
length = len(array)

total_case = list(permutations(array, length))

def simulation(case):
    value = 0
    for i in range(1, len(case)):
        value += abs(case[i] - case[i-1])

    return value

answer = 0
for case in total_case:
    answer = max(answer, simulation(case))

print(answer)

문제 설명

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이 과정

일반적인 BFS 문제하고는 좀 다르다. 왜냐하면 걸을때는 1초 걸리고, 순간이동을 하는 경우에는 0초 걸리기 때문에 최단 시간을 구하기 애매하다. 따라서, 현재 위치에서 가능할때까지 2배만 사용해서 쭉 가보고, 왼쪽, 오른쪽으로 이동하는 방식으로 구현해야 한다.

1. BFS를 진행한다.
   • 덱에는 [현재 위치, 현재 위치까지의 비용] 형식으로 저장한다.
   • 현재 위치가 동생이 있는 위치인지 검사한다.
   • 현재위치 * 2, 현재위치 + 1, 현재위치 - 1 순서로 덱에 넣는다.
     • 이 때, 현재 위치 * 2를 덱의 왼쪽에 삽입한다. => 가장 먼저 현재 위치 * 2를 방문하도록 함.
     • 나머지의 경우는 덱의 오른쪽에 삽입한다.
     • 이런 식으로 구현하면, 예시로 비용이 2라고 할 때, N-1, N-2, N, N+1, N+2 위치에서 순간이동을 하여 갈수 있는 모든 지점을 갈 수 있다.
2. BFS 진행 중에, 동생이 있는 위치에 오게 되면 비용을 출력하고 종료한다.

소스 코드

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

queue = deque([[N, 0]])
visited = [False] * 100001
visited[N] = True
answer = int(10e9)
while queue:
    next_x, cost = queue.popleft()
    if next_x == K:
        answer = cost
        break

    for step in [next_x * 2, next_x+1, next_x-1]:
        if 0 <= step <= 100000 and not visited[step]:
            if step == next_x * 2:
                queue.appendleft([step, cost])
            else:
                queue.append([step, cost+1])
            visited[step] = True

print(answer)

문제 설명

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

풀이 과정

1. 점들을 오름차순으로 정렬해 준다. => 이진탐색을 하기 위함.
2. 입력받은 선분의 두개의 점을 이진탐색을 진행한다.
   • 파이썬의 bisect_left, bisect_right 함수를 사용한다. 간단하게 설명하자면 bisect_left(x, a)는 a를 x에 삽입할 때, 삽입해야 할 위치를 리턴한다. left와 right의 차이는 왼쪽에 삽입할지, 오른쪽에 삽입할지의 차이이다.
   • 선분의 작은 점은 bisect_left => 작은 점을 포함하게 하기 위해
   • 선분의 큰 점은 bisect_right => 큰 점을 포함하게 하기 위해
   • 위의 두 인덱스 사이에 있는 모든 점들이 선분 안에 포함된다.
3. 점의 개수를 리턴해주면 된다.

소스 코드

from bisect import bisect_left, bisect_right
import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
points = list(map(int, sys.stdin.readline().rstrip().split()))
points.sort()

for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    lidx = bisect_left(points, a)
    ridx = bisect_right(points, b)
    print(ridx - lidx)

문제 설명

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1≤N≤200000)과 K(1≤K≤100)가 주어진다.

둘째 줄에는a1,a2,...an{a_1, a_2, ... a_n}$이 주어진다 (1≤ai≤100000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

풀이 과정

• 원래는 투 포인터 문제 분류여서 투포인터 방식으로 구현하려 했으나.. 큐로 구현하는게 훨씬 편할 것 같아서 큐로 구현, 구현해보니 투포인터랑 크게 다를건 없는거 같다.

1. 원소의 개수를 매번 큐에서 세는 경우, 시간 초과가 발생할 수도 있으니 딕셔너리로 원수의 개수를 추가하면서 세줌.
2. 원소를 순차적으로 접근하면서 추가하였을 때, 원소의 개수가 K개를 넘는 경우
   • 추가한 원소를 빼줄때까지 큐의 왼쪽에서부터 빼준다.
3. 매 순간 queue가 언제 최대 길이가 되는지 저장해둔 다음, 마지막에 출력해주면 된다. (최장 연속 부분 수열의 길이)

소스 코드

import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
numbers = list(map(int, input().rstrip().split()))
sequence = set()
dup_count = {i:0 for i in range(1, 100001)}
answer = 0

queue = deque()
for number in numbers:
    queue.append(number)
    dup_count[number] += 1
    # number에서 중복 문제 걸림
    if dup_count[number] > K:
        # number가 나올때까지 queue에서 싹 빼주어야 함.
        while queue:
            temp = queue.popleft()
            dup_count[temp] -= 1
            if temp == number:
                break
    answer = max(answer, len(queue))

print(answer)