백준(BOJ) 12892 생일 선물(Python)

문제 내용

 

두 포인터 문제.

선물의 가격을 기준으로 입력값을 오름차순 정렬한 리스트를 생성하고, s, e 두 포인터를 이용해 문제를 해결했다.

(e가 가리키는 선물의 가격) - (s가 가리키는 선물의 가격)이 d 미만인 경우 k에 e가 가리키는 선물의 만족도를 더한다.

그러다가 d 이상인 경우 ans를 max(k,ans)로 갱신하고, (e가 가리키는 선물의 가격) - (s가 가리키는 선물의 가격)이 d 미만이 될 때까지 s를 옮기며 k를 수정한다.

e가 n인 경우 이를 종료한다.

마지막에는 ans를 한 번 더 갱신해주는데, 이는 목록 중 가장 비싼 선물과 싼 선물의 값 차이가 d 미만인 경우 ans가 위 과정에서 갱신되지 않기 때문이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
from itertools import permutations
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,d=map(int,input().split())
L=[list(map(int,input().split())) for i in range(n)]
L.sort()
s=0
e=0
ans=0
k=0
while True:
    if L[e][0]-L[s][0]<d:
        k+=L[e][1]
        e+=1
    else:
        ans=max(k,ans)
        p=L[e][0]-d+1
        while p>L[s][0]:
            k-=L[s][1]
            s+=1
    if e==n:
        break
ans=max(k,ans)
print(ans)

pypy로 제출해서 통과했다.