백준 27527. 배너 걸기

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

27527번: 배너 걸기

'''
N개의 구간마다 물체가 정확히 하나씩 존재
배너는 연속된 N개구간 중 M개의 구간에 결쳐서 걸어야 함
연속된 M개 구간에서 같은 높이가 90%이상이면 걸 수 있음!
배너를 걸 수 있는지 확인

1차 시도: 하나하나 count 해봤다가 시간초과됨
2차 시도: 슬라이딩 윈도우 알고리즘 서치함 + Counter 함수 서치함 -> 시간초과됨
3차 시도: Counter 함수 버리고 리스트 이용
'''

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

def can_hang_banner(N, M, heights):
    count = [0] * (10**6 + 1) # 각 높이의 빈도수를 저장할 리스트
    max_freq = 0 # 최대 빈도수
    for i in range(N):
        if i >= M: # 윈도우의 크기가 M이 되면(윈도우 단체로 한칸 이동)
            # 윈도우에서 빠져나간 높이의 빈도수 감소
            count[heights[i-M]] -= 1
        # 현재 높이의 빈도수 증가
        count[heights[i]] += 1
        # 최대 빈도수 갱신
        if max_freq < count[heights[i]]:
            max_freq = count[heights[i]]
        if i >= M-1: # 윈도우가 완전히 구성되었을 때(배너걸 수 있는지 유무 판단)
            if max_freq >= 0.9 * M: # 가장 빈도수가 높은 요소의 빈도수가 0.9 * M 이상이면
                return "YES" # 배너를 걸 수 있음
    return "NO" # 배너를 걸 수 없음

print(can_hang_banner(N,M,sections))

생각해보면 간단한데...감을 잃어서 그런가 많이 고민했다...