문제

BOJ 14464 바로가기
본 문제의 저작권은 백준 온라인저지에 있습니다.

코드

import sys
input=sys.stdin.readline

C,N=map(int, input().split())
chicken=[int(input()) for _ in range(C)]
cow=[]
visited=[False]*(C+1)
now_cow=0
now_chi=0
answer=0
for i in range(N):
    cow.append(list(map(int, input().split())))

# 작은 순서로 정렬
chicken.sort()
cow.sort(key=lambda x:(x[1]))	# 마감이 빠른 순서로 정렬

# 소 돌면서 남아있는 닭 찾기
for co in cow:
    for k in range(C):
        if not visited[k] and co[0]<=chicken[k]<=co[1]:
            visited[k]=True
            answer+=1
            break

print(answer)

틀렸던 코드

C,N=map(int, input().split())
chicken=[int(input()) for _ in range(C)]
cow=[]
now_cow=0
now_chi=0
answer=0
for i in range(N):
    cow.append(list(map(int, input().split())))

chicken.sort()
cow.sort(key=lambda x:(x[1],x[0]))
# 치킨이 안움직여야함(소만커지는경우도 있음)
while now_chi<C and now_cow<N:
    if cow[now_cow][0]<=chicken[now_chi]<=cow[now_cow][1]:  # 범위충족
        answer+= 1
        now_cow+= 1
        now_chi+= 1
    elif cow[now_cow][0]>chicken[now_chi]:  # 치킨이 더 작음
        now_chi += 1
    elif cow[now_cow][1]<chicken[now_chi]:  # 치킨이 더 큼
        now_cow += 1

print(answer)

• 소랑 닭을 해당 기준에 맞게 정렬해두고 소 범위가 넘어가면 소의 인덱스를 하나 추가 , 닭의 범위가 넘어가면 닭의 인덱스를 하나 추가하는 방식으로 수정하였으나 예외가 발생하였다

  예외) 소: 2~3, 1~10 닭: 1,2
  기댓값: 2
  출력값: 1

• 그래서 순서를 반대로 오름차순 후 내림차순으로 정렬하였더니 다음과 같은 예외가 발생하였다

  소: 1~6, 4~5 닭: 4,6
  기댓값: 2
  출력값: 1

• 결국 기존 풀이를 버리고 닭을 다 찾아야한다고 판단하였다.(pypy3으로 해야 시간초과가 발생하지 않는다.)