[BOJ] 9576. 책 나눠주기

문제링크

t = int(input())

for _ in range(t):
  result = 0
  n, m = map(int, input().split())
  books = [False] * (n + 1)
  reqs = []
  for _ in range(m):
    reqs.append(list(map(int, input().split())))

  reqs.sort(key = lambda x:x[1]) # b를 기준으로 오름차순
  
  while reqs:
    a, b = reqs.pop(0)
    for i in range(a, b + 1):
      if not books[i]: # False이면, 나눠줄 수 있음
        result += 1
        books[i] = True
        break
  print(result)

음.. 구글링해서 문제 이해하구 풀었던 문제.. !
처음에 각 book마다 deque를 선언해서 popleft, append, peek(ex. queue[0])를 통해
학생을 넣고, 빼고 하였다
내 틀린 코드를 보자면....

from collections import deque
t = int(input())

for _ in range(t):
  result = 0
  n, m = map(int, input().split())
  books = [deque() for _ in range(n + 1)]
  before = -1
  for student in range(m):
    a, b = map(int, input().split())
    # 각 책 번호별로 배열..? 큐..?   
    # 각 변호별로 큐를 생성하면 어떻게 될까.. 
    check = False
    append_check = False
    for num in range(a, b + 1):
      if len(books[num]) == 0:
        books[num].append(student)
        append_check = True
      elif check == False:
        if books[num][0] == before:
          check = True
          
      else: # 이전 학생이 전에 존재했다면
        books[num].popleft()
        books[num].append(student)
        append_check = True
        if student == m - 1: break
    
    if append_check == True : result += 1
    before = student

  print(result)

매우 복잡하게 짜놓았다. 50%에서 자꾸 틀렸다
나는 a, b를 입력받을 때마다 처리하도록 했는데 정답 코드를 보니 정말 복잡하게 짜놓았더라
하지만

3 3
1 2
1 3
2 2

이 예시의 답은 3이 나와야 하는데, 2가 나왔다.
나는 정렬을 고려하지 않고 문제를 푼 것이다.
b를 기준으로 오름차순 정렬을 하면, 학생들에게 최대로 많이 나눠줄 수 있다.
이젠 해설을 보지않고,, 생각나도록 연습해야겠다

21.07.06

import sys

input = sys.stdin.readline

t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  books = [False] * (n + 1)
  requests = []
  for _ in range(m):
    a, b = map(int, input().split())
    requests.append((a, b))

  requests.sort(key=lambda x:x[1]) # b번을 기준으로 오름차순

  cnt = 0
  # 앞에서부터 search하여 값이 False이면 나눠준다.
  for a, b in requests:
    for i in range(a, b + 1):
      if not books[i]:
        books[i] = True
        cnt += 1
        break
  print(cnt)

해설 보고 풀었다..
b를 기준으로 정렬하고, for문 search는 a부터!