Sort: 백준 1764 문제

https://www.acmicpc.net/problem/1931

1. 문제 복기...

솔직히 이유라고 할 것도 없이 이번 문제는 이걸 어떻게 풀어야할지 감도 못 잡았다..

전체를 풀어다가 list에서 sort 시키고 해당하는 시간대를 하나씩 빼면서 전체 개수를 줄여나가야하나 ...?

뭐 이런 생각도 했는데 아니 하 ... 이거 알고리즘 분류를 내가 잘 해내서 보면서 딱 이게 무슨 문제인지 알아차려야 하는데 참 이게 아직은 잘 안되는 것 같다...

그리고 솔직히 정렬 문제인거 알았어도 내가 잘 풀었을지 의문이다. 30분 정도 공책에 이것저것 적다가 끝나버렸는데 너무도 간단한 풀이여서 놀랐다...

그냥 진짜 말 그대로 "정렬" 시키고 끝나는 시간대보다 시작시간이 앞에있으면 제외하고 같거나 뒤에이쓰면 그걸 시작시간대로 놓고...

이래도 되는 것이 다음 두가지 가설이 맞기 때문이다.

1. 끝나는 시간이 가장 이른 순서대로 tuple을 리스트에서 정렬시키는 경우 시작 시간이 언제든 가장 첫번째 오는 시간대가 뒤에 가장 많은 회의 갯수를 보장할 수 있다.
2. 그 논리는 연속하는 순서에서도 보장된다.

딱 이 두가지 가설이 맞기 때문이다.
이걸 생각을 못했다.

이 논리를 끝까지 들고가서 마지막 for문에서도 그냥 시작시간이 끝나는 시간과 같거나 그 후면 바로 통과시키고 count를 1 추가하면 된다.

2. 정답 코드

import sys

def main():
    N = int(sys.stdin.readline().rstrip())
    
    # 회의시간 초기화
    meetings = []
    
    # 회의 시간 리스트로 받기
    for _ in range(N):
        meeting = tuple(map(int, sys.stdin.readline().rstrip().split()))
        meetings.append(meeting)
    
    # 끝나는 시간 기준 정렬하고 끝나는시간 같으면 시작 시간 기준 정렬
    meetings.sort(key=lambda x: (x[1], x[0]))
    
    
    # 그리디 알고리즘 적용
    count = 0
    end_time = 0
    
    for start, end in meetings:
        if start >= end_time:
            count += 1
            end_time = end
    
    print(count)


if __name__ == "__main__":
    main()