백준 1931 - 파이썬 2차원 배열 정렬, 그리디 알고리즘

풀이

N = int(input())

cnt = 0
meeting =[]

for i in range(N):
    meeting.append(list(map(int, input().split())))


# meeting = [[1, 3], [3, 2], [5, 8]] 형태로 저장
# meeting[0][1] = 2

# 2차원 배열 정렬하는 방법
# meeting.sort(key = lambda x:x[num])
# num 인덱스를 기준으로 정렬된다
# num = 0 -> 첫번째 값 기준 / num = 1 -> 두번째 값 기준
# 내림차순하는 방법 : x 앞에 -붙이기
# meeting.sort(key = lambda x: -x[num])

meeting.sort(key=lambda x:(x[1], x[0]))

# 비교할 기준 숫자(가장 작은 끝 시간)
num = meeting[0][1]

for j in range(1, len(meeting)):
    if num <= meeting[j][0]: # 가장 작은 끝 시간과 시작 시간 비교해서 시작시간이 크면 다음 회의 시작
        num = meeting[j][1] # 회의 끝난 후 회의 끝난 시간 num에 저장
        cnt += 1
# 반례
# 5
# 1 1
# 2 3
# 3 4
# 4 5
# 5 6
# 정답 : 5 / 출력 : 6 
# 첫 회의가 시작시간 끝시간 같을 때 반례

# 5
# 5 5
# 6 6
# 5 6
# 6 7
# 7 7
# 정답 : 5 / 출력 : 4
    
print(cnt + 1) # num(첫 회의)은 cnt에 포함이 안 됐으므로 +1 해준다.


# 첫 번째 오류 : 첫 회의가 같을 때를 맨 밑에 프린트 문에서 +1을 해줬는데 
# for문에서도 카운트를 하고 있었다 -> for문의 시작을 j = 0이 아닌 1로 시작해서 해결

# 두 번째 오류 : 끝 시간이 같을 경우에 시작 시간이 빠른 순으로 다시 정렬해야했다.
# meeting.sort(key=lambda x:x[1])
# 나는 이렇게 끝 시간이 빠른 순으로만 정렬을 했다. 
# 따라서, meeting.sort(key=lambda x:(x[1], x[0]))으로 끝 시간이 빠른 순으로 정렬 후 -> 시작 시간이 빠른 순으로 정렬
# 이차원 배열에서 정렬 저렇게도 가능함! (a 기준으로 정렬 후 b 기준으로 정렬)

💡 2차원 배열 정렬 방법

A.sort(key = lambda x : x[num]) : A 배열의 num 인덱스 기준으로 정렬
num = 0 : 첫번째 인덱스(행) 기준 정렬 / num = 1 : 두 번째 인덱스(열) 기준 정렬

A.sort(key = lambda x : -x[num]) : 내림차순 (x앞에 -붙이면 내림차순)

if) 1차적으로 행으로 정렬한 후, 2차적으로 열로 정렬하고 싶다면?
A.sort(key = lambda x : (x[0], x[1])) : 이렇게 괄호 안에 2개 선언하기

💡 그리디 알고리즘인 이유?

그리디 알고리즘 : 선택의 순간마다 최적의 상황만을 쫓아서 최종 해답에 도달

• 그리디 알고리즘 적용 조건 2가지
  ① 탐욕적 선택 속성(Greedy Choice Property)
  : 앞 선택이 이후 선택에 영향 을 미치지 않는다.

  👉 시작 시간 / 종료 시간은 고정되어 있기 때문에 앞 회의에 따라서 회의시간이 바뀌는 것이 아니다.

  ② 최적 부분 구조(Optimal Substructure)
  : 문제에 대한 최종 해결법은 부분 문제에 대한 최적 해결법으로 구성된다.

  👉 부분적으로 종료시간이 가장 빠른 회의순으로 진행하는 회의부터 처리하는 방식으로 해결해나가면 최종적으로 최대 회의 수가 도출된다.
  

※ 이 문제에서 주의할 점
: 종료시간만 고려하는 것이 아니라, 종료시간이 같다면,
시작시간을 비교하여 시작시간이 빠른 순으로 정렬하여 해결해야한다.

# 반례
# 5
# 5 5
# 6 6
# 5 6
# 6 7
# 7 7
# 정답 : 5 / 출력 : 4

만약, 종료시간만 고려했다면 (5, 5) -> (6, 6) -> (6, 7) -> (7, 7)로 도출되는데
실제로는 (5, 5) -> (5, 6) -> (6, 6) -> (6, 7) -> (7, 7)이 최대 회의 수이다.
따라서, 종료시간이 같다면 다음과 같이 시작시간이 빠른 순으로 정렬해야한다.

# 5
# 5 5
# 5 6
# 6 6
# 6 7
# 7 7