[백준] 20922. 겹치는 건 싫어

겹치는 건 싫어

분류

• 투 포인터

문제 설명

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

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

입력

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.

둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력

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

예제 입력 & 출력

입력: 
9 2
3 2 5 5 6 4 4 5 7

출력: 
7

문제풀이

이 문제는 투 포인터 문제로, 아래와 같이 풀 수 있다.

1. list의 최대값만큼의 길이를 가진 배열을 생성한다. (sequence 배열 생성)
2. 투포인터를 위해 left, right 변수를 생성하고 right가 arr 길이에 도달할 때까지 loop를 돈다.
3. sequence 배열에서 해당 idx값이 M(중복횟수) 보다 작으면 값을 1 추가하고 right를 전진시킨다.
4. 조건에 만족하지 않으면 left idx 값을 1 빼주고, left를 전진시킨다.
5. 결과값 변수에 수열의 길이를 할당한다.
6. 출력 끝

python 문제 풀이

N, M = map(int, input().split())
arr = list(map(int, input().split()))


sequence = [0] * (max(arr) + 1) # 1. arr의 최대 값만큼의 길이를 가진 배열 생성
left, right = 0, 0 # 투포인터 index
result = 0 # 최대값을 저장할 변수

# 2. N만큼 Loop
while right < N:
    # 3. 배열에서 해당 idx값이 M보다 작으면 더해준다.
    if sequence[arr[right]] < M:
        sequence[arr[right]] += 1
        right += 1
    # 4. left를 전진해주고 해당 값을 1 빼준다.
    else:
        sequence[arr[left]] -= 1
        left += 1
    
    # 5. result에 수열의 길이(right-left)를 할당한다.
    result = max(result, right - left)
    
print(result)