(그리디)회의실 배정

1. 문제

 

2. 내가 쓴 코드 + 알고리즘

 

<내가 쓴 코드 + 알고리즘>

#조건 확인
#각 회의에 대해 -> 회의 시작 시간 & 끝나는 시간 주어진다
#회의 중복 x 최대 수의 회의를 찾아라.
#회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다

#튜플의 형태로 저장..? : enumerate

n = int(input()) #회의의 수
start = list(range(5))
end = list(range(5))
cnt=list[100000]

#meeting = list(range(n)) #크기가 5인 리스트화 #index:0,1,2,3,4
for i in range(n):
    start[i],end[i] = map(int,input().split())

for x in range(n):
        if(end[x]<= start[x+1]): # 앞의 끝나는시간과, 뒤의 시작시간 비교
            

       
# (1,4)이 스타트 -> (4,6) (5,7) 회의 가능
# (2,3)이 스타트 -> (3,5) (4,6) (5,7) 회의 가능
# (3,5) 이 스타트-> (5,7) 회의 가능
# (4,6 ) 이 스타트->  회의 못함
# (5,7) 이 스타트-> 회의 못함

>>

잘못 생각한 점 :

- 간단할 수 있는걸 배열 index를 사용해서 어렵게 접근했다.

-아직 파이썬 문법에 구멍이 많다. 리스트는 생각은 했지만, 접근을 못했고, 람다함수는 생각도 못했다.

잘한 점:

 - if(end[x]<= start[x+1]) 이 조건에서 볼 수 있듯, 끝나는 시간이 시작 시간보다 같거나 작을 때, 회의 가능하다는 조건을 잘 생각했다.

 - 최대 '갯수'를 세는 것이므로, cnt를 도입한 것을 잘했다

 -map함수를 잘 이용했다.

 

3. 답

n = int(input()) #회의의 수

#시작시간과 끝 시간이 있는 각각의 회의들을, 리스트에 저장해야함 -> 빈리스트 하나 만들자
meeting = []

for i in range(n):
    start,end = map(int,input().split()) 
    meeting.append((start,end)) #시작 시간과 끝나는 시간을 튜플 형태로 넣었다. #append함수 사용
#meeting.sort() #앞 자료 값 기준으로 정렬.


# 끝나는 시간 기준으로 sorting해준다. 정렬하는 key의 기준 :람다함수 사용
meeting.sort(key= lambda x: (x[1],x[0])) # x는 튜플 자료. x[1]:end가 우선순위로 하라는 것. x[0]:start가 두 번째 정렬 순위 되라는 것.
et=0 # 끝나는 시간 기록하기 위한 용도
cnt=0 #갯수 세기 용도
for start,end in meeting:
    if start>=et:
        et=end #회의를 진행 했으니, et초기화
        cnt+=1 #카운팅

print(cnt)

 

 

4. 새로 알게된 내용

 

[빈 리스트 생성]
list_name = []

[튜플 형태로 리스트에 값 넣기]
list_name.append((x,y))

[sorting]

•  보통은, 앞에서 순차적으로 정렬이 된다.
  ex) meeting.sort() 
   -> 앞 자료값인 x를 기준으로 오름차순으로 튜플 값들이 정렬됨
•  정렬 기준을 바꾸고 싶을 때(기억할 것)
  meeting.sort(key= lambda x: (x[1],x[0]))
   -> 두 번째 값인 x[1]을 첫 번째 값인 x[0]보다 기준을 우선으로 두라는 것 -> 두 번째 원소 기준의 오름차순을 보는 것

[튜플 탐색]
tuple_name = (val1,val2)일 때
for val1,val2 in tuple_name:
   if val1 > val2 ~~...

[람다함수]

람다 함수(lambda function)는 파이썬에서 간단한 함수를 정의할 때 사용하는 방법 중 하나입니다.

람다 함수는 이름이 없는 익명 함수로, 한 줄로 작성됩니다. 일반적인 함수 정의와 달리, def 키워드를 사용하지 않습니다.

람다 함수는 보통 다른 함수의 인수로 사용되며, 한 줄로 작성되기 때문에 간단한 연산이나 처리를 수행하는 데 사용됩니다.

예를 들어, meeting.sort(key= lambda x: (x[1],x[0]))에서는 sort() 메서드의 key 매개 변수에 람다 함수가 사용되었습니다. 이 람다 함수는 x[1]과 x[0]을 반환하는데, 이것은 x의 두 번째와 첫 번째 요소를 기준으로 정렬하라는 의미입니다.

 

예를 들어, x가 리스트 [a, b]일 때, x[0]은 a이고 x[1]은 b입니다.

따라서, meeting.sort(key= lambda x: (x[1],x[0])) 코드는 meeting 리스트의 요소들이 리스트 [a, b] 형태로 저장되어 있다고 가정했을 때, 먼저 각 요소에서 x[1] (즉, b)을 기준으로 오름차순으로 정렬하고, x[1]이 같은 요소들에 대해서는 x[0] (즉, a)을 기준으로 오름차순으로 정렬합니다.

예를 들어, meeting = [[1, 4], [2, 3], [1, 2]]인 경우,

• 먼저 x[1]을 기준으로 정렬하면 [1, 2], [2, 3], [1, 4] 순으로 정렬됩니다.
• 그 다음, x[1]이 같은 요소들에 대해서는 x[0]을 기준으로 정렬하면, [1, 2], [2, 3], [1, 4] 순으로 최종적으로 정렬됩니다.

즉, meeting 리스트는 [[1, 2], [2, 3], [1, 4]] 순으로 정렬됩니다.