[Atcoder] ABC 326 C - Peak

이번에도 C까지만 풀고 쉬러 다녀왔습니다.

 

어제 인적성 검사만 두개를 보고왔어서 상당히 피곤했었네요.

 

결론적으로 x부터 시작하는 길이 M의 half-open interval에 몇개의 선물이 들어있는지 물어보는 문제입니다. 

 

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
A = list(map(int,input().split()))
dict = {}
for i in range (0,N):
    if A[i] in dict:
        dict[A[i]] += 1
    else:
        dict[A[i]] = 1
A = list(set(A))
A.sort()
answer = []

if len(A) == 1:
    print(dict[A[0]])
else:
    ans = []
    i = 0
    j = 0
    cnt = 0
    while True:
        if A[j] - A[i] < M:
            cnt += dict[A[j]]
            j += 1
        else:
            cnt -= dict[A[i]]
            i += 1
        if j == len(A) or i == len(A):
            ans.append(cnt)
            break
        else:
            ans.append(cnt)
            continue
    print(max(ans))

아이디어로서는 

먼저 선물의 좌표를 받은 뒤, key를 좌표, value를 선물의 갯수로 해서 딕셔너리를 만들었어요.

 

그리고 중요한 부분으로, 좌표를 크기순으로 정렬합니다.

그 뒤, 투포인터 + 슬라이딩 형태로 길이 조절을 해가면서 길이의 최댓값을 구했습니다.

(위에서 받은 value값을 추가하거나 빼거나 하는 등)

 

몇번이나 에러가 나서 왜 그러지? 싶었는데 if len(A) == 1 부분에서 한 점에 다수가 나올 수 있다는 것을 간과했습니다.

 

예를 들어 1,1,1,1,1,1,1,1,1 같은 ... 

 

D까지 빨리 풀고싶네요. 화이팅 !