프로그래머스, 체육복(greedy algorithm)
https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3
체육복을 도둑맞은 상황에서 체육복이 2개인 사람들이 체육복을 빌려주어서 체육 수업을 들을 수 있는 최대 학생 수를 구하는 문제다.
번호의 앞뒤로 빌려주는것만이 가능한 상황이라 조건문을 짜기 굉장히 까다로웠는데 이것을 어떻게 간단하게 바꿀 수 있을지 고민해봤다.
모든 경우의 수를 조건문으로 짜지 않고, 각 위치에서 앞에 사람이 빌려줄수있는 경우에 받기만 하면 그것이 최대값이 될 수 있다고 생각이 들어 코딩을 시작했다.
나의 코드
인덱스를 이용한 정직한 방법이다.
cloth = [1 for _ in range(n)]
for i in lost:
cloth[i-1]-=1
for i in reserve:
cloth[i-1]+=1
for i in range(1,n):
if (cloth[i]==2 and cloth[i-1]==0) or (cloth[i]==0 and cloth[i-1]==2):
cloth[i] = cloth[i-1] = 1
answer = [c for c in cloth if c>0]
return len(answer)
다른 사람의 풀이
파이썬의 효율적인 내장함수를 사용한 풀이이다. 좀 더 Pythonic 하지만 reserve 리스트가 정렬된 상태에서 작동하는 코드이므로 내 코드가 시간복잡도 면에서는 이득이지 않나 싶다...
reserve.sort()
new_reserve = [r for r in reserve if r not in lost]
new_lost = [l for l in lost if l not in reserve]
for r in new_reserve:
front = r-1
back = r+1
if front in new_lost:
new_lost.remove(front)
elif back in new_lost:
new_lost.remove(back)
return n-len(new_lost)
Author And Source
이 문제에 관하여(프로그래머스, 체육복(greedy algorithm)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jun112465/프로그래머스-체육복greedy-algorithm저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)