백준(BOJ) 13334 철로(Python)

문제 내용.

 

스위핑 문제.

구간의 길이가 d 이하인 구간에 대해, 끝값을 기준으로 구간을 선택해줬다.

끝값을 기준으로 구간을 선택하게 되면 현재 선택한 끝값을 변화시킬 때마다 해당 범위에 속할 수 없는 초깃값이 나오는데,

이 초깃값을 갖는 구간의 개수를 미리 세어두면 끝값이 변화할 때마다 해당 범위에 속할 수 없게 되는 초깃값을 갖는 구간의 개수만 빼주며 계속 구간을 선택해나가면 된다.

 

우선 문제를 더 쉽게 풀기 위해 입력받은 h와 o에 대해, 더 작은 값을 h, 더 큰 값을 o로 설정했다.

두 값은 서로 바뀌어도 상관이 없기 때문이다.

그 후에는 h를 기준으로 [h,o] 구간의 길이가 d 이하인 것의 개수를 세어 딕셔너리에 저장했다.

[h,o]로 구성된 리스트를 o를 기준으로 오름차순 정렬하고,

각 구간에 대해 o가 바뀌지 않는다면 c에 1을 더하고, o가 바뀌었다면 ans=max(ans,c)로 수정해준다.

그 후 범위에 속할 수 없는 초깃값을 갖는 구간의 개수를 c에서 빼주고, 계속해서 구간을 세어준다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
D={}
n=int(input())
L=[]
for i in range(n):
    a,b=map(int,input().split())
    a,b=min(a,b),max(a,b)
    L.append([a,b])
d=int(input())
for i in range(n):
    if L[i][1]-L[i][0]<=d:
        if L[i][0] not in D:
            D[L[i][0]]=1
        else:
            D[L[i][0]]+=1
ans=0
if D:
    s=min(D)
    e=s+d
    L.sort(key=lambda x:(x[1],x[0]))
    keys=list(D.keys())
    keys.sort()
    p=0
    c=0
    ans=0
    for i in range(n):
        if s<=L[i][0] and L[i][1]<=e:
            c+=1
        else:
            ans=max(ans,c)
            e=L[i][1]
            s=e-d
            while p<len(keys) and keys[p]<s:
                c-=D[keys[p]]
                p+=1
            if s<=L[i][0] and L[i][1]<=e:
                c+=1
    ans=max(ans,c)
print(ans)

 

요즘 코포도 그렇고 정렬된 배열에서 쭉 탐색하다 값이 변화할 때 뭔가를 처리하는 문제가 자주 보이는 것 같다.

값이 변화할 때 뭔가를 처리하는 것이 아직 쉽지 않다.