알고리즘 유형별 기출문제: 그리디
💻 1. 모험가 길드
난이도🖤🤍🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB | 핵심 유형
📌2021/01/03 작성 코드
# 입력
n = int(input())
fear = list(map(int, input().split()))
fear.sort() # 공포도 오름차순으로 정렬
# 알고리즘
schedule = [0]*n # i번째 모험가가 그룹을 이루면 schedule[i]=0보다 큰 정수
count = 0 # 그룹 수 세는 count
for i in range(n):
current_fear = fear[i]
# 공포도가 그룹을 이룰 수 있는 사람 수보다 큰 경우, 그룹핑이 불가능
if i - current_fear + 1 < 0:
continue
# 공포도가 그룹을 이룰 수 있는 사람 수보다 작거나 같은 경우
else:
# 그룹핑 가능 여부
grouping = True
# 만약 이미 그룹을 이룬 사람이 있다면 그룹핑 실패
for j in range(i-current_fear+1, i + 1):
if schedule[j] != 0:
grouping = False
break
# 그룹핑 가능할 때
if grouping:
count += 1 # 그룹 카운트 증가
for j in range(i-current_fear+1, i + 1):
schedule[j] = count # 같은 그룹은 count로 할당해준다. (꼭 count아니어도 0이 아닌 숫자로 할당해주면 됨)
# 출력
# print(schedule)
print(count)
💭 아이디어
최대 그룹 수를 만들기 위해서는, 위 그림에서처럼 최소 공포도를 가진 사람을 우선으로 그룹을 만들어야 한다. (Case2 참고) 즉, 그룹 내 구성원을 최소화 하겠다는 뜻과 마찬가지이다!
공포도 X인 사람을 기준으로 만든 그룹에는 공포도가 X보다 큰 사람이 존재할 수 없기 때문에 공포도를 오름차순으로 정렬하여 grouping을 했다.
🤓 문제 해설
일단 공포도를 기준으로 오름차순으로 정렬을 수행해보자. 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인하며, 그룹에 포함될 모험가의 수를 계산할 수 있다. 만약에 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 그룹을 결성할 수 있을 것이다.
예를 들어 문제에서의 예시 입력은 다음과 같다.
[2, 3, 1, 2, 2]
가장 먼저 5명의 공포도를 오름차순으로 정렬하면 다음과 같이 구성된다.
[1, 2, 2, 2, 3]
이제 앞에서부터 공포도를 하나씩 확인하며, '현재 그룹에 포함된 모험가의 수'가 '현재 확인하고 있는 공포도' 보다 크거나 같다면, 이를 그룹으로 설정하면 된다. 현재 예시에서는 다음과 같이 2개의 그룹이 형성된다. 남은 2명의 모험가는 그룹에 속하지 못하고 그대로 남아 있게 된다.
[(1), (2, 2), 2, 3]
이러한 방법을 이용하면 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 된다. 따라서 최대한 많은 그룹이 구성되는 방법이므로, 항상 최적의 해를 찾을 수 있다.
🤓 답안 예시
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수
for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
count += 1 # 현재 그룹에 해당 모험가를 포함시키기
if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1 # 총 그룹의 수 증가시키기
count = 0 # 현재 그룹에 포함된 모험가의 수 초기화
print(result) # 총 그룹의 수 출력🤔 리뷰
주의..! 의식의 흐름 리뷰
- 처음엔 매우 어렵다고 생각했다. 문제의 해설에 지나치게 의존했기 때문이다. 이처럼 해설이 트릭인 경우가 있나...? 계속 보면서 그림으로 정리하니 해결방법이 떠오르기 시작했다.
- 나는 내 아이디어를 그대로 구현하기 위해 변수를 쓸 데 없이 많이 사용했는데, 답안 예시의 깔끔한 코드를 보고 깜짝 놀랐다... 아이디어를 들여다보고 간결하게 정리할 수 있는 능력이 필요하겠다
- 생각을 좀 더 하면 복잡도를 훨씬 훨씬 훠얼씬 줄여낼 수 있겠다.
- 헉 지금 드는 생각인데 이거 아마 온라인 저지로 돌렸으면 내 코드는 시간 초과 떴을 수도 있겠는데? N의 최대가 100,000인데 시간 제한이 1초이면 O(NlogN)알고리즘으로 풀어야 한다는 것 아닌가. 아이고.
- 답안 코드가 정답이네, 내 껀 시간제한에 걸릴듯? 다시 답안 참고해서 짜봐야겠다
