https://www.acmicpc.net/problem/3078
코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
students = [input() for _ in range(n)]
window = dict()
answer = 0
for i in range(k+1):
length = len(students[i])
if length in window:
answer += window[length]
else:
window[length] = 0
window[len(students[i])] += 1
for i in range(k+1, n):
length = len(students[i])
prev_length = len(students[i-(k+1)])
window[prev_length] -= 1
if length in window:
answer += window[length]
else:
window[length] = 0
window[len(students[i])] += 1
print(answer)
크기가 k인 슬라이딩 윈도우를 한 칸씩 밀어내며 슬라이딩 윈도우 내에 좋은 친구쌍이 몇 개 있는지 확인하는 방법으로 풀었다. 슬라이딩 윈도우 내의 원소들의 값을 저장하기 위한 자료구조로는 딕셔너리를 사용했다.
슬라이딩 윈도우를 한 칸씩 옮길 때마다 범위에서 밀려난 높은 등수(`i-(k+1)`)의 학생은 빼고, i번째 등수의 학생을 슬라이딩 윈도우에 넣는다.
'문제풀이 > 투포인터' 카테고리의 다른 글
[Python/파이썬] 백준 1940번 주몽 (0) | 2025.04.21 |
---|---|
[Python/파이썬] 백준 15565번 귀여운 라이언 (0) | 2025.01.27 |
[Python/파이썬] 백준 15831번 준표의 조약돌 (1) | 2025.01.03 |
[Python/파이썬] 백준 1253번 좋다 (0) | 2024.06.28 |
[Python/파이썬] SW Expert Academy 20728번 공평한 분배 2 (0) | 2024.06.13 |