그리디 알고리즘(2)

체력 테스트 후 우수한 학생을 선발하고자 한다. 키, 몸무게 중 적어도 하나는 다른 사람보다 커야 한다는 선발 기준이 있을 때 (데이터 중복은 없다고 가정) 몇 명의 학생을 선발할 수 있을까?

 

 (키, 몸무게) 튜플 형식으로 리스트에 넣은 후

키를 기준으로 내림차순 정렬한다.

 

그렇다면 정렬 후 앞에 나오는 사람은 항상 키가 크고, 나중에 등장하는 사람은 항상 앞사람보다 키가 작다.

따라서 몸무게가 지금까지 선발된 사람 중 가장 크다면 선발 가능하다.

 

그리고 최대 몸무게(largest)를 갱신하고 선발된 학생 수(cnt)를 증가시킨다.

	키	몸무게	최대 몸무게	선발 여부
A	183	65	0->65	O
B	181	60	65	X
C	180	70	65->70	O
D	175	67	70	X
E	172	72	70->72	O

body=[]
for i in range(n):
    t, w=map(int, input().split())	# 튜플
    body.append((t, w))
body.sort(reverse=True)	# 키를 기준으로 내림차순 정렬
largest=0	# 현재 최대 몸무게
cnt=0
for x, y in body:
    if y>largest:
        largest=x
        cnt+=1
print(cnt)

 

 

이중for문을 돌리는 건 비효율적................................

list=[]
for i in range(n):
    t, w=map(int, input().split())
    list.append((t, w))
cnt=0
for t, w in list:
    for at, aw in list:
        if t>=at or w>=aw:
            continue
        else:
            break
    else:
        cnt+=1
print(cnt)

# 정답은 출력되지만 비효율적..