[백준] 1931번

그녕·2023년 3월 5일
0

백준 1931번

그리디

💗내 풀이💗

이 문제는 많이 봤었는데도 보니깐 어떻게 풀어야할지 감이 안왔다. 걸리는 시간으로 정렬을 해야하는지 어떻게 해야하는지 못 풀겠어서 답을 보았다..ㅜ

  1. 시작은 입력 받은 거를 append를 해서 리스트로 만들어줘야한다.

    • [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]] 이 된다.
  2. 그 다음에는 1. 끝나는 시간으로 정렬을 해줘야한다. 2. 시작 순서로 정렬을 해줘야한다.가 포인트였는데 끝나는 시간이 빠른것이 키 포인트다. 그치만 코드 상으로 sorted를 해줄때는 2번부터 해주고 1번을 해줘야한다. 왜냐하면 코드상으로는 시작순으로 먼저 정렬을 해주고 끝나는 순으로 다시 오름차순을 해줘야지 끝나는 순으로 완성이 되어있기 때문이다. 이렇게 두번 sorting을 해주고 나면 끝나는 시간이 빠른 순으로 오름차순 정렬이 되고 끝나는 시간이 같은 경우에는 시작 순서가 빠른게 먼저 정렬이 되기 때문이다.

    • 시작 순서로 오름차순 정렬해주면 : [[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]] 이 된다.

    • 마치는 순서로 오름차순 정렬해주면: [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]] 이 된다.

    • 여기서 또 몰랐던 점은 sorted 함수였다. 전에 배웠었는데도 또 까먹었다.

  1. 정렬이 다 되었다면, 그 다음에는 그 다음 시작 시간이 그 전의 애의 끝 시간보다 크거나 같아야지 회의실을 쓸수 있기 때문에 cnt++을 해준다. 그리고 last인 끝 시간을 업로드 해준다.
    • 여기서 몰랐던 점은 time이라는 리스트에 [0,2]가 담겨있으면 for문을 쓸때 그냥 바로
      for i, j in time으로 쓸수 있다는 것이었다.

🟡Sorted 함수 정리

sorted(정렬할 데이터)
sorted(정렬할 데이터, reverse 파라미터)
sorted(정렬할 데이터, key 파라미터)
sorted(정렬할 데이터, key 파라미터, reverse 파라미터)
이 문제에서 쓴건 3번째이다.
sorted(time,key = lambda x: x[0])은 time이라는 리스트에서 첫번째 원소로 오름차순 정렬하는 것이다.
또 주의 해야할 점이 sorted는 새로운 리스트를 만들어주는 거라서 꼭 정렬한 다음에
time= sorted(time) 이런식으로 해줘야 한다.
(sort는 원래의 리스트를 변형시키는 거라서 그냥 해줘도 됨)

💗내 코드💗

N = int(input())
time=[]
for _ in range(N):
    a,b= map(int, input().split())
    time.append([a,b])
time= sorted(time,key=lambda x: x[0])
time= sorted(time,key=lambda x: x[1])
last=0
cnt=0
for i,j in time:
    if i >= last:
        cnt+= 1
        last = j
print(cnt)

0개의 댓글