그리디 알고리즘 : 모험가 길드 - 파이썬 (python)

* 방법1 (내림차순 정렬) → 오답

아이디어: 카드를 큰 수 부터 정렬한 후 그 숫자만큼씩 묶으면 된다고 생각했다.

예를 들어 N이 5이고 공포도가 2 3 1 2 2인 경우,

2 3 1 2 2를 내림차순으로 정렬하고 -> 3 2 2 2 1

3 2 2 / 2 1

3 2 2 를 그룹1로 묶어주고 2 1 을 그룹2로 묶어준다.

그룹1은 그룹 1에서 가장 큰 수인 3만큼 묶어주고

그룹2는 그룹 1을 제외한 리스트에서 가장 큰 수인 2만큼 묶어주었다.

직접 풀이한 방식이며 돌려본 테스트 케이스로는 방법2와 결과값이 모두 동일하게 나왔다.

(수정) N=6이고 공포도가 4 3 3 3 3 2 인 경우 

내림차순 정렬 4 3 3 3 / 3 2 -> result는 1인데

오름차순 정렬 2 3 / 3 3 3 / 4 -> result가 2여야 하므로 오류 ! → 오름차순 정렬로 풀어야 함

#방법1 (내림차순 정렬) -직접 푼 방법
n = int(input()) #인원 수
k = list(map(int, input().split())) #공포도

result = 1
li = [] #인덱스 리스트
x = 0 #인덱스 번호
k.sort(reverse=True) #내림차순 정렬

while True:
    if n == 1 | k[0] == n : #인원 수가 1이거나 최고 공포도와 인원 수가 같은 경우
        break

    li.append(x)
    x += k[x]
    result += 1

    if x+k[x] == n:
        break

print(result)

* 방법2 (오름차순 정렬)

아이디어: 공포도를 기준으로 오름차순으로 정렬한다.

공포도가 가장 낮은 모험가부터 하나씩 확인하며, 그룹에 포함될 모험가의 수를 계산할 수 있다.

현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면, 그룹을 결성할 수 있다.

2 3 1 2 2 오름차순 정렬 -> 1 2 2 2 3

앞에서부터 공포도를 하나씩 확인하며,

'현재 그룹에 포함된 모험가의 수'가 '현재 확인하고 있는 공포도'보다 크거나 같다면, 이를 그룹으로 설정한다.

1 / 2 2 / 2 3

현재 예시에서는 위와 같이 2개의 그룹이 형성되고 남은 2명의 모험가는 그룹에 속하지 못하고 그대로 남아있게 된다.

 

#방법2 (오름차순 정렬) -교재 예시
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)

 

 

 

 

github.com/501501/codingTest/commit/7095eb2bff8734d5d1a41b7270d386530e1a3d9c

#11-01 · 501501/codingTest@7095eb2