[알고리즘] BOJ 20922 겹치는 건 싫어 #Python

김상현·2022년 11월 22일

목록 보기

233/301

[BOJ] 20922 겹치는 건 싫어 바로가기

📍 문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 4255 1436 1086 33.769%
문제
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $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$ )

📍 출력

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

📍 풀이

💡 고찰

200,000 개의 입력 제한을 보고 너무 많은 입력이 주어졌기 때문에, 투 포인터 이거나 이진 탐색일 수 있겠다고 추측하고 해당 알고리즘을 문제에 적용하려고 하였으나 도저히 방법을 찾을 수 없어서 검색을 통해 문제를 해결하였다.
투 포인터, 이진 탐색을 이용한 문제를 풀 때마다 항상 접근이 너무 어려운 것 같다.
투 포인터, 이진 탐색 기초에 해당하는 알고리즘 문제를 풀면서 경험을 얻어야 할 것 같다.

📌 문제 풀이

✏️ [1] 투 포인터 알고리즘

while end < N:
    if numberCount[A[end]] >= K:
        numberCount[A[start]] -= 1
        start += 1
    else:
        numberCount[A[end]] += 1
        end += 1
        answer = max(answer, end - start)

수열의 시작과 마지막 인덱스 값을 갖는 start, end 변수의 초기값은 0으로 초기화 한다.
start 인덱스부터 end 인덱스까지 해당하는 부분 수열이 K 개 이상의 중복이 없는지 검사한다.
검사 방법은 end 의 값을 증가시키면서 end 인덱스에 해당하는 숫자의 개수를 증가시킨다.
만약 end 인덱스에 해당하는 숫자의 개수가 K 를 넘는다면 end 의 진행은 중단시키고 start 의 값을 증가시키면서 start 인덱스에 해당하는 숫자의 개수를 감소시킨다.
start 의 값을 증가하는 중 end 인덱스에 해당하는 숫자의 개수가 K 와 같아진다면 다시 end 의 값을 증가시키는 연산을 반복한다.

✍ 코드

from sys import stdin
from collections import defaultdict

def solution(N, K, A):
    answer = 0
    start, end = 0, 0

    # [1] 수열에 주어진 각 정수의 개수
    numberCount = defaultdict(int)

    # [2] 투 포인터
    while end < N:
        if numberCount[A[end]] >= K:
            numberCount[A[start]] -= 1
            start += 1
        else:
            numberCount[A[end]] += 1
            end += 1
            answer = max(answer, end - start)

    return answer

# input
N, K = map(int,stdin.readline().split())
A = list(map(int,stdin.readline().split()))

# result
result = solution(N, K, A)
print(result)