백준 20922 겹치는 건 싫어 파이썬

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

20922번: 겹치는 건 싫어

​

처음에 문제를 잘못 이해했다. 원소가 중복되는 갯수가 K 이상인 경우로 경계 조건을 오인했다. 예를 들어 5 5 2 2 2라는 값이 들어오면, 중복되는 것이니 총 5개의 원소가 중복된다고 판단했다. 그런데 실제 문제는 약간 다르다.

​

중복되는 원소가 있는 경우, 중복된 원소들 중 최대 갯수가 K이상인 경우를 발라내는 것이었다. 예를 들어 5 5 2 2 2 라고 하면, 현재 중복된 값은 3이다. 이걸 바탕으로 문제를 다시 풀었다.

​

​

1. 완전탐색으로 가능한지 확인해본다. n번째 원소에 대해 각각 n번씩 확인해야한다. 예를 들어 n, n-1 , n - 2 ... n 확인해야하니 n^2의 시간복잡도가 발생한다. 현재 주어진 n은 20만이기 때문에 완전탐색은 안된다.
2. 두 포인터로 문제 없이 접근할 수 있는지 확인했다.
3. R,L로 나누어 확인한 다음에 각각의 중복 갯수를 체크한다. 그리고 중복된 갯수가 K보다 작으면 R을 증가하고, K보다 크면 L을 증가한다. 이 때, L,R이 이미 최대한 영역을 가리키기 때문에 뒷쪽을 다시 돌아볼 필요가 없다. 왜냐하면 뒤로 돌아가면 적어도 중복된 갯수가 항상 K와 같거나 크기 때문이다.
4. 따라서 두 포인터로 접근 가능하다.

​

​

​

나는 이 두 가지 경우에서 헤맸다.

1. L을 증가시키는 경우, 현재 C_CNT를 감소시키지 않아서 인덱스 에러가 발생했다.
2. L을 증가시키는 경우, 이 값이 최대값인지를 판별할 때 반례가 발생했다. 현재 위치를 지웠을 때, 그 인덱스의 값이 0일 경우 항상 최대값이라고 생각했다. 그런데 실제로는 이 위치의 값이 최대값이면, 이 값을 인덱스에서 지웠을 때 0인 경우가 항상 최대값이다.

​

​

​

import sys

# 입력
n,k = map(int,sys.stdin.readline().split())
my_list = list(map(int,sys.stdin.readline().split()))



# 변수 초기화
l,r,ans,c_cnt, temp_cnt = 0,-1,0,0,0
num_list = [0 for _ in range(100000 + 1)]
mem_list = [set() for _ in range(200000 + 1)]
for i in my_list:
    mem_list[0].add(i)

while True :

    # 문자열 상태 판별
    if c_cnt <= k :
        ans = max(ans,temp_cnt)

    # 두 포인터 이동
    if c_cnt <= k :
        r +=1
        if r >= n :
            break

        # R이 가리키는 현재 숫자를 가져온다.
        now_num = my_list[r]

        # R이 가리키는 현재 숫자의 카운트를 올린다.
        num_list[now_num] += 1
        c_cnt = max(c_cnt, num_list[now_num])

        # 현재 수열의 길이를 증가시킨다.
        temp_cnt +=1


        # 현재 숫자의 카운트가 얼마인지 본다.
        now_num_cnt = num_list[now_num]
        pre_num_cnt = now_num_cnt-1

        # 집합에 초기화 한다
        # 1. 이전에 있었던 건 집합에서 제거한다
        # 2. 현재 위치를 집합에 추가한다.
        mem_list[now_num_cnt].add(now_num)
        mem_list[pre_num_cnt].remove(now_num)




    else :
        # l이 가리키는 현재 숫자가 무엇인지 가져온다.
        now_num = my_list[l]

        # 현재 숫자 카운트를 가져온다
        now_num_cnt = num_list[now_num]
        num_list[now_num] -= 1
        # 다음 숫자 카운트를 가져온다.
        next_num_cnt = now_num_cnt - 1

        # 업데이트 해준다.

        mem_list[now_num_cnt].remove(now_num)
        mem_list[next_num_cnt].add(now_num)

        # 현재 위치 카운트가 0이면, 얘가 최대값이다.
        if len(mem_list[now_num_cnt]) == 0 and now_num_cnt == c_cnt:
            c_cnt = next_num_cnt

        l += 1
        if l > r :
            break
        temp_cnt -=1




print(ans)