- 4주차 과제 - 대표 선발(그리디 알고리즘)
- 사용 언어 : python
- 해결 날짜 : 2021-04-02
- 느낀점 및 해결 과정 :
- 이번 과제는 지원자의 수와 각 지원자의 두 과목의 성적이 입력되면 list에 tuple 형태로 저장하고, tuple의 first 값을 기준으로 정렬하여 second 값을 비교하는 방법을 통해 해결하였다.
- 우선 사용자로부터 지원자의 수(n), 지원자의 두 과목 성적을 입력 받아 공백을 기준으로 잘라서 A, B 임시 변수에 저장하고, int형으로 변환한 뒤 tuple의 형태로 subject라는 list에 저장하였다.
그 후 sort() 함수로 subject list 속 tuple의 first 값을 기준으로 정렬하였고, 대표팀으로 선발된 학생의 수를 구하는 함수인 find_num_of_selected을 적용한다.
find_num_of_selected에서 인자로 받은 given_list는 first 값으로 정렬이 되어 있으므로 second 값만을 비교하면 된다. for문으로 given_list를 돌며 현재 인덱스(temp)로부터 이전 인덱스들의 second 값 중 가장 작은 값(flag)와 비교하여 temp가 flag보다 작다면 대표팀으로 선발 가능하다는 소리이므로 flag를 temp로 다시 설정해주고, count 값을 1 증가시켜준다.
여기서 정렬된 list의 첫번째 인덱스의 first 값은 1등으로 무조건 선발이 가능하므로 두번째 인덱스부터 시작하되, count 변수의 초기값은 1로, flag 변수의 초기값은 given_list[0][1]로 설정해 주었다.
최종적으로 count값을 반환하여 만들 수 있는 대표팀의 최대 인원수를 출력하였다.
- 과제를 해결하며 처음에는 완전 탐색인 O(N^2)밖에 떠오르지 않았는데, 입력의 개수가 100000개 이므로 무조건 O(NlogN)보다는 작은 시간 복잡도의 알고리즘을 생각해 냈는데, sort 함수를 통하여 O(NlogN)를 생각해 해결할 수 있었다.
- 시간 복잡도 :
- 지원자의 수, 지원자의 두 과목 성적 입력 받기 : N
- list 속 tuple의 first 값을 기준으로 정렬(sort) : NlogN
- 대표팀으로 선발된 학생 수 구하기(given_list를 돌되 두번째 인덱스부터 시작하므로) : N-1
- 따라서 최종 시간 복잡도는 N + NlogN + N – 1 = NlogN + 2N + 1이므로 가장 높은 차수인 NlogN을 제외하고는 전부 제외되어 O(NlogN)이 된다.
- 코드
```python
# 대표팀으로 선발된 학생의 수를 구하는 함수 - O(N)
def find_num_of_selected(given_list):
# 정렬된 list의 첫번째 인덱스의 first 값은 1로 무조건 선발가능
# first 값으로 정렬이 되어 있으므로 second 값을 비교한다.
# 현재 인덱스(temp)로부터 이전 인덱스들의 second 값 중 가장 작은값(flag)과 비교하여
# temp가 flag보다 작다면 대표팀으로 선발 가능
count = 1
flag = given_list[0][1]
for idx in range(1, len(given_list)):
temp = given_list[idx][1]
if temp < flag:
flag = temp
count += 1
if flag == 1:
break
return count
# 사용자로부터 지원자의 수, 지원자의 2 과목 성적 입력 받기 - O(N)
subject = list()
n = int(input())
for i in range(0, n):
A, B = input().split(" ")
subject.append((int(A), int(B)))
# list 속 tuple의 first 값을 기준으로 정렬 - O(NlogN)
subject.sort()
num_of_selected = find_num_of_selected(subject)
print(num_of_selected)
```