Baekjoon 20922 | 겹치는 건 싫어(Python)

📌문제

SILVER1 / 두 포인터

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

[성능 요약]

메모리: 53288 KB, 시간: 232 ms

[분류]

두 포인터

 

[문제 설명]

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

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

[입력]

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

둘째 줄에는 a1,a2,...ana1,a2,...an이 주어진다 (1≤ai≤1000001≤ai≤100000)

[출력]

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

 

[예제]

 

📌문제 분석 및 설계

now 인덱스를 옮기면서 같은 원소가 K개를 초과하면 start인덱스를 앞으로 옮기는 식으로 풀었다.

시간이 타이트하기때문에 두포인터를 쓰지 않으면 시간초과가 발생했다.

 

최종 설계는 아래와 같이 했다.

1. 요소의 개수를 저장하는 n_ai배열을 k로 초과했다(요소를 발견할때마다 -1하는 방식 채택) .

2. now(현재 인덱스)를 0부터 1씩 증가하며 요소의 개수를 센다.

3. 만약 n_ai[now]의 value값이 0보다 작아진다면 now를 증가하지 않고 start를 증가시킨다. 이 때, 원래 start 요소는 연속배열에서 빠지기 때문에 원래 start요소의 개수를 +1해준다. 또한, now 요소의 개수도 +1 해준다.=> n_ai[now] 의 value값이 0보다 클때까지 now는 계속 같은 위치, start만 전진하는 방식.

4. 출력시 수열의 길이와 result 중 최대값을 print해준다. 그냥 result를 출력하게 된다면, 아래와 같은 반례를 맞이하게 된다.

2 1
1 2

 

↓

다 풀고 나니 step3번이 비효율적이라 생각해서 chatgpt에게 코드를 줘봤더니,

n_ai[now]의 value값이 0보다 작아졌을때, 해당 조건에 만족하지 않을때까지 start를 옮겨주면 됐다..!

📌소스 코드

#실제 내가 작성한 코드
n,k=map(int,input().split())
a=list(map(int,input().split()))

n_ai=[k]*100001
result=1

start,now=0,0
while now!=n:
    temp=a[now]
    n_ai[temp]-=1
    if n_ai[temp]<0:
        result=max(result,now-start)
        n_ai[a[start]]+=1
        n_ai[temp]+=1
        start+=1
    else:
        now+=1
print(max(result,now-start))

#chatgpt가 수정해 준 코드
n, k = map(int, input().split())
a = list(map(int, input().split()))

count = [0] * 100001  # 숫자의 등장 횟수를 저장할 배열
start = 0
result = 0

for end in range(n):
    count[a[end]] += 1
    
    # k번 초과 등장하면 start 포인터를 이동시켜 해결
    while count[a[end]] > k:
        count[a[start]] -= 1
        start += 1

    result = max(result, end - start + 1)

print(result)