Greedy) 모험가 길드

모험가 길드

<이것이 취업을 위한 코딩테스트다, 311p, 나동빈, 한빛미디어>

☝첫번째 접근

역순 정렬으로 큰 수부터 접근하여 그룹을 형성한 후
슬라이스를 이용해서 그룹지어진 원소들 제거했다.

N = 8
fears = [1, 2, 4, 2, 2, 1, 1, 3]

fears = sorted(fears, reverse=True)
count = 0

for i in fears:
    if i > len(fears):
        break
    elif i == len(fears):
        count += 1
        break
    fears = fears[i:]
    count += 1

print(count)

이 코드의 문제점은,
for문을 도는 fears가 for문 내에서 변형되어도 변형 전의 리스트를 기억하고있어서 for문을 형성해서 슬라이스를 잘라도 4->2->2->... 순서로 원소가 반복된다.

deque를 사용해서 문제를 해결해보려했지만 코드가 점점 산으로 가버렸다.

🙌올바른 접근

오름차순 정렬로 작은 수 부터 접근하여 그룹을 형성해야한다.
for문 안에서 리스트는 변형시키지 않고 count를 이용해서 그룹에 몇 개의 원소가 포함됐는지만 체크해준다.

N = 8
fears = [1, 2, 4, 2, 2, 1, 1, 3]
fears = sorted(fears)
count = 0
result = 0

for f in fears:
    count += 1
    if f == count:
        result += 1
        count = 0

print(result)

✍피드백

for문 안에서는 해당 리스트를 변형하지 않는게 간단하게 문제를 해결하는데 유리함.
오름차순으로 접근할지 내림차순으로 접근할지 결정하는 것은 굉장히 중요하다...😭