[김태원 알고리즘] 씨름 선수 (그리디)

사용 언어: Python3

문제

풀이

내 풀이 - 1. 2중 for문 사용

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

lst.sort() # 키가 작은 순으로 정렬
cnt = N
for i in range(N):
    for j in range(i+1,N):
        if lst[i][1] < lst[j][1]: # 나를 키로 이기는 사람들 중에 나보다 무거운 사람이 있다면 나는 탈락
            cnt -= 1
            continue
print(cnt)

• 성공

내 풀이 - 2. any() 사용

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

lst.sort()
cnt = N
for i in range(N):
    if any(lst[i][1] < lst[j][1] for j in range(i+1, N)): # ✅ any()
        cnt -= 1
print(cnt)

• any(iterable): 인자로 받은 반복가능한 자료형(iterable)중 단 하나라도 참(True)이 있으면 참(True)를 반환하는 함수이다.
  반대로 모든 요소가 거짓(False)인 경우에만 거짓(False)을 반환한다.

내 풀이 - 3. max() 사용

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

lst.sort() # 키가 작은 순으로 정렬
cnt = 0
print(lst)
for i in range(N):
    # 나보다 키가 큰 사람들 중에 내가 몸무게가 최대여야 함 (나보다 몸무게 큰 사람 있으면 나는 탈락)
    if lst[i] == max(lst[i:N], key=lambda x:x[1]): # ✅ 몸무게 기준 max
        cnt += 1 # 선발
print(cnt)

다른 풀이

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

lst.sort(reverse=True) # 키가 큰 순으로 정렬
largest = -1 # 최댓값
cnt = 0
for x in lst:
    if x[1] > largest: # 몸무게 비교
        largest = x[1] # 최댓값 갱신
        cnt += 1 # 선발
print(cnt)

• 설명
  • 키 순 내림차순 정렬: [[183, 65], [181, 60], [180, 70], [172, 67], [170, 72]]
  • 몸무게만 보면, [65, 60, 70, 67, 72]
    • 맨 앞 사람은 키가 가장 큰 사람이니까 무조건 선발
    • 몸무게 largest를 65로 갱신
    • 이후부터는 키가 점점 작아지니 몸무게 largest를 max로 갱신하는 사람만 선발된다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기