[백준 20922번] 파이썬 - 겹치는 건 싫어

백준 20922_겹치는 건 싫어

시간제한 1초(추가시간x), 메모리제한 1024MB

# 조건

• 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다.
• 특히 수열에 같은 원소가 여러 개 들어 있는 수열을 싫어한다.
• 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
• 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.
• 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성하시오.

입력

• 첫 줄에 정수 N (1 <=N<= 200,000)과 K (1<=K<=100)가 주어진다.
• 둘째 줄에 a1, a2, ..... , an 이 주어진다

출력

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

# 접근 방법

처음 - 틀린 방법

• 꼭 처음부터 시작해야 되는 것이 아니다.
• 중간부터 시작하는 것이 최장 길이를 가질 수도 있다.
• 따라서, 2차원 배열 dp와 2중 for문으로 풀어준다.
  • 0~n까지 for문 하나 - 인자 i
  • start ~ i 까지 반복문 - 인자 j을 만들어준다.
• dp[N의 수][max(arr)+1] 로 만들며, arr을 순회해준다.
  • 현재 순회중인 인덱스 전의 2차원 배열을 돌며 +1을 해주며 k가 넘는 경우 start+1을 해준다.
• 또한 N 크기의 일차원 배열하나를 만들어 K가 넘는다면, 현재 인덱스 - j 를 해주어 최장 길이를 기록해준다.
• 이후 max를 이용해 출력

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, K = map(int, input().split())  
arr = [*map(int, input().split())]  

dp = [[0]*(max(arr)+1) for _ in range(N)]  
start = 0  
result = [0] * N  
for i in range(N):  
    idx = arr[i]  
    for j in range(start, i+1):  
        dp[j][idx] += 1  
        if dp[j][idx] > K:  
            result[j] = i - j  
            start += 1  
        else:  
            result[j] += 1  
print(max(result))

second

• 투 포인터를 이용하여 풀어주면 된다.
• counter 리스트는 max(arr])+1로 만들어주고
• 해당 숫자가 몇 번 나왔는지 체크한다.
• left, right 포인터는 0부터 시작하며
• K가 넘어가는 경우 counter[left 포인터가 가르키는 값] -1 을 해주고 left +1을 해준다.

N, K = map(int, input().split())  
numbers = list(map(int, input().split()))  
left, right = 0, 0  

counter = [0] * (max(numbers) + 1)  
answer = 0  
while right < N:  
    if counter[numbers[right]] < K:  
        counter[numbers[right]] += 1  
        right += 1  
    else:  
        counter[numbers[left]] -= 1  
        left += 1  
    answer = max(answer, right - left)  
print(answer)